{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sliding Window Median"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #sliding-window #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #滑动窗口 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: medianSlidingWindow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #滑动窗口中位数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。</p>\n",
    "\n",
    "<p>例如：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>[2,3,4]</code>，中位数是 <code>3</code></li>\n",
    "\t<li><code>[2,3]</code>，中位数是 <code>(2 + 3) / 2 = 2.5</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <em>nums</em>，有一个长度为 <em>k</em> 的窗口从最左端滑动到最右端。窗口中有 <em>k</em> 个数，每次窗口向右移动 <em>1</em> 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<p>给出 <em>nums</em> = <code>[1,3,-1,-3,5,3,6,7]</code>，以及 <em>k</em> = 3。</p>\n",
    "\n",
    "<pre>\n",
    "窗口位置                      中位数\n",
    "---------------               -----\n",
    "[1  3  -1] -3  5  3  6  7       1\n",
    " 1 [3  -1  -3] 5  3  6  7      -1\n",
    " 1  3 [-1  -3  5] 3  6  7      -1\n",
    " 1  3  -1 [-3  5  3] 6  7       3\n",
    " 1  3  -1  -3 [5  3  6] 7       5\n",
    " 1  3  -1  -3  5 [3  6  7]      6\n",
    "</pre>\n",
    "\n",
    "<p> 因此，返回该滑动窗口的中位数数组 <code>[1,-1,-1,3,5,6]</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以假设 <code>k</code> 始终有效，即：<code>k</code> 始终小于等于输入的非空数组的元素个数。</li>\n",
    "\t<li>与真实值误差在 <code>10 ^ -5</code> 以内的答案将被视作正确答案。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sliding-window-median](https://leetcode.cn/problems/sliding-window-median/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sliding-window-median](https://leetcode.cn/problems/sliding-window-median/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,-1,-3,5,3,6,7]\\n3', '[1,2,3,4,2,3,1,4,2]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "\n",
    "        arr = []\n",
    "        l = 0\n",
    "        res = []\n",
    "\n",
    "        for r in range(len(nums)):\n",
    "            bisect.insort(arr, nums[r])\n",
    "            while len(arr) > k:\n",
    "                arr.pop(bisect.bisect_left(arr, nums[l]))\n",
    "                l += 1\n",
    "            if len(arr) == k:\n",
    "                res.append((arr[k//2]+arr[(k-1)//2])/2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        window = []\n",
    "\n",
    "        # binary search for insert index of target value in a ascending order list (which is window here)\n",
    "        def findWindowInsertIdex(lst, target):\n",
    "            left, right = 0, len(lst) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if window[mid] < target:\n",
    "                    left = mid + 1\n",
    "                elif window[mid] > target:\n",
    "                    right = mid - 1\n",
    "                else: # window[mid] == target\n",
    "                    return mid\n",
    "            return left\n",
    "\n",
    "        for i in range(n):\n",
    "            insert_idx = findWindowInsertIdex(window, nums[i])\n",
    "            window[insert_idx:insert_idx] = [nums[i]]\n",
    "\n",
    "            if len(window) > k:\n",
    "                prev_val = nums[i - k]\n",
    "                remove_idx = findWindowInsertIdex(window, prev_val)\n",
    "                window[remove_idx: remove_idx + 1] = []\n",
    "            \n",
    "            if len(window) == k:\n",
    "                median = (window[k // 2] + window[(k - 1) // 2]) / 2\n",
    "                res.append(median)\n",
    "        \n",
    "        return res\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums, k):\n",
    "        window = sorted(nums[:k])\n",
    "        res = []\n",
    "        for a, b in zip(nums, nums[k:] + [0]):\n",
    "            res.append((window[k//2] + window[~(k//2)]) / 2.)\n",
    "            window.remove(a)\n",
    "            bisect.insort(window, b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums, k):\n",
    "        window = sorted(nums[:k])\n",
    "        res = []\n",
    "        for a, b in zip(nums, nums[k:] + [0]):\n",
    "            res.append((window[k//2] + window[~(k//2)]) / 2.)\n",
    "            window.remove(a)\n",
    "            bisect.insort(window, b)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        median = lambda a: (a[(len(a)-1)//2] + a[len(a)//2]) / 2\n",
    "        a = sorted(nums[:k])\n",
    "        res = [median(a)]\n",
    "        for i, j in zip(nums[:-k], nums[k:]):\n",
    "            a.pop(bisect.bisect_left(a, i))\n",
    "            bisect.insort_left(a, j)\n",
    "            res.append(median(a))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: list, k: int) -> list:\n",
    "        order_k = nums[:k]\n",
    "        order_k.sort()\n",
    "\n",
    "        res = []\n",
    "        res.append(self.cal(order_k, k))\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            in_val = nums[i]\n",
    "            out_val = nums[i-k]\n",
    "\n",
    "            order_k.remove(out_val)\n",
    "            in_idx = bisect.bisect(order_k, in_val)\n",
    "            order_k.insert(in_idx, in_val)\n",
    "            res.append(self.cal(order_k, k))\n",
    "\n",
    "        return res\n",
    "\n",
    "    def cal(self: any, nums_list: list, k: int) -> float:\n",
    "        mid = k // 2\n",
    "        if k % 2 == 0:\n",
    "            return (nums_list[mid-1] + nums_list[mid]) / 2\n",
    "        else:\n",
    "            return nums_list[mid]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        if k == 0: return []\n",
    "        if k > len(nums): return []\n",
    "        ans = []\n",
    "        n_now = sorted(nums[:k-1])\n",
    "        for i in range(k-1, len(nums)):\n",
    "            bisect.insort_left(n_now, nums[i])\n",
    "            ans.append((n_now[k//2] + n_now[k//2-(1-k%2)])/2)\n",
    "            n_now.remove(nums[i - k+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        data = sorted(nums[:k])\n",
    "        res = []\n",
    "        res.append(self.get_median(k, data))\n",
    "        for i in range(len(nums) - k ):\n",
    "            data.remove(nums[i])\n",
    "            bisect.insort_left(data,nums[i+k])\n",
    "            res.append(self.get_median(k, data))\n",
    "        return res\n",
    "\n",
    "    def get_median(self, k, temp_list):\n",
    "        if k%2 != 0 :\n",
    "            return temp_list[(k-1)//2]\n",
    "        else:\n",
    "            return (temp_list[(k-1)//2] + temp_list[k//2])/2\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        l = SortedList()\n",
    "        ans = [0]*(n-k+1)\n",
    "        for i in range(n):\n",
    "            l.add(nums[i])\n",
    "            st = i - k + 1\n",
    "            if i >= k:\n",
    "                l.remove(nums[st-1])\n",
    "            if st >= 0:\n",
    "                ans[st] = (l[k//2] + l[(k-1)//2])/2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        ans = []\n",
    "        window = SortedList()\n",
    "        for i in range(len(nums)):\n",
    "            window.add(nums[i])\n",
    "            if len(window) == k:\n",
    "                ans.append(window[k // 2] if k & 1 else (window[k // 2] + window[k // 2 - 1]) / 2)\n",
    "                window.remove(nums[i - k + 1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        median = lambda a: (a[(len(a)-1)//2] + a[len(a)//2]) / 2\n",
    "        a = sorted(nums[:k])\n",
    "        res = [median(a)]\n",
    "        for i, j in zip(nums[:-k], nums[k:]):\n",
    "            a.pop(bisect.bisect_left(a, i))\n",
    "            bisect.insort_left(a, j)\n",
    "            res.append(median(a))\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        import bisect\n",
    "        arr = []\n",
    "        left = 0\n",
    "        res = []\n",
    "        for right in range(len(nums)):\n",
    "            bisect.insort(arr, nums[right])\n",
    "            while len(arr) > k:\n",
    "                arr.pop(bisect.bisect_left(arr, nums[left])) ### 把最左边的直接移动走，扔掉窗口的前一个数\n",
    "                left += 1\n",
    "            if len(arr) == k:\n",
    "                res.append((arr[k // 2] + arr[(k - 1) // 2]) / 2.0)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "### 相当于利用sortedlist 减少了一个排序的时间，然后每次利用这个已经排序好的lst，类似于heap\n",
    "### 就是为了避免排序的时间！！！ 跟求最大值一模一样\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        lst = SortedList(nums[:k - 1])\n",
    "        for i in range(k - 1, n): #### 这是最后一个数\n",
    "            lst.add(nums[i])\n",
    "            if k % 2 == 0:\n",
    "                ans.append((lst[k // 2] + lst[k // 2 - 1]) / 2)\n",
    "            else:\n",
    "                ans.append(lst[k // 2])\n",
    "            lst.discard(nums[i - k + 1]) ### 扔掉滑动窗口的前一个数\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        sl = SortedList()\n",
    "        left = 0\n",
    "        ans = []\n",
    "        for i, x in enumerate(nums):\n",
    "            sl.add(x)\n",
    "\n",
    "            while i - left > k - 1:\n",
    "                sl.remove(nums[left])\n",
    "                left += 1\n",
    "\n",
    "            if i - left == k - 1:\n",
    "                if k % 2 == 0:\n",
    "                    ans.append((sl[k // 2 - 1] + sl[k // 2]) / 2)\n",
    "                else:\n",
    "                    ans.append(sl[k // 2])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        r = []\n",
    "        x = nums[:k]\n",
    "        x.sort()\n",
    "        if k % 2==1:\n",
    "            r.append(x[k//2])\n",
    "        else:\n",
    "            r.append((x[k//2]+x[k//2-1])/2)\n",
    "        def remove(a,st,ed):\n",
    "            if x[st] == a:\n",
    "                return st\n",
    "            if x[ed] == a:\n",
    "                return ed\n",
    "            mid = (st+ed) // 2\n",
    "            if x[mid] == a:\n",
    "                return mid\n",
    "            if x[mid]< a:\n",
    "                return remove(a,mid+1,ed)\n",
    "            else:\n",
    "                return remove(a,st,mid-1)\n",
    "        def insert(a,st,ed):\n",
    "            if ed <= st:\n",
    "                return ed\n",
    "            mid = (st+ed) // 2\n",
    "            if x[mid] == a:\n",
    "                return mid\n",
    "            elif x[mid] < a:\n",
    "                return insert(a,mid+1,ed)\n",
    "            else:\n",
    "                if mid >= 1:\n",
    "                    return insert(a,st,mid-1)\n",
    "                else:\n",
    "                    return 0\n",
    "        for i in range(1,len(nums)-k+1):\n",
    "            if k == 1:\n",
    "                r.append(nums[i])\n",
    "                continue\n",
    "            end = nums[i+k-1]\n",
    "            st = nums[i-1]\n",
    "            pos = remove(st,0,k-1)\n",
    "            x.pop(pos)\n",
    "            pos = insert(end,0,k-2)\n",
    "            if end >= x[pos]:\n",
    "                x.insert(pos+1,end)\n",
    "            else:\n",
    "                x.insert(pos,end)\n",
    "            if k % 2==1:\n",
    "                r.append(x[k//2])\n",
    "            else:\n",
    "                r.append((x[k//2]+x[k//2-1])/2)\n",
    "\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        sl = SortedList(nums[:k - 1])\n",
    "        ans = []\n",
    "        for i in range(k - 1,len(nums)):\n",
    "            sl.add(nums[i])\n",
    "            if k % 2 == 0:\n",
    "                ans.append((sl[k // 2 - 1] + sl[k // 2])/2)\n",
    "            else:\n",
    "                ans.append(sl[k//2])\n",
    "            sl.remove(nums[i - k + 1])\n",
    "        return ans\n",
    "# sortedList\n",
    "class SortedList:\n",
    "    def __init__(self, iterable=[], _load=200):\n",
    "        \"\"\"Initialize sorted list instance.\"\"\"\n",
    "        values = sorted(iterable)\n",
    "        self._len = _len = len(values)\n",
    "        self._load = _load\n",
    "        self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]\n",
    "        self._list_lens = [len(_list) for _list in _lists]\n",
    "        self._mins = [_list[0] for _list in _lists]\n",
    "        self._fen_tree = []\n",
    "        self._rebuild = True\n",
    "\n",
    "    def _fen_build(self):\n",
    "        \"\"\"Build a fenwick tree instance.\"\"\"\n",
    "        self._fen_tree[:] = self._list_lens\n",
    "        _fen_tree = self._fen_tree\n",
    "        for i in range(len(_fen_tree)):\n",
    "            if i | i + 1 < len(_fen_tree):\n",
    "                _fen_tree[i | i + 1] += _fen_tree[i]\n",
    "        self._rebuild = False\n",
    "\n",
    "    def _fen_update(self, index, value):\n",
    "        \"\"\"Update `fen_tree[index] += value`.\"\"\"\n",
    "        if not self._rebuild:\n",
    "            _fen_tree = self._fen_tree\n",
    "            while index < len(_fen_tree):\n",
    "                _fen_tree[index] += value\n",
    "                index |= index + 1\n",
    "\n",
    "    def _fen_query(self, end):\n",
    "        \"\"\"Return `sum(_fen_tree[:end])`.\"\"\"\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    "\n",
    "        _fen_tree = self._fen_tree\n",
    "        x = 0\n",
    "        while end:\n",
    "            x += _fen_tree[end - 1]\n",
    "            end &= end - 1\n",
    "        return x\n",
    "\n",
    "    def _fen_findkth(self, k):\n",
    "        \"\"\"Return a pair of (the largest `idx` such that `sum(_fen_tree[:idx]) <= k`, `k - sum(_fen_tree[:idx])`).\"\"\"\n",
    "        _list_lens = self._list_lens\n",
    "        if k < _list_lens[0]:\n",
    "            return 0, k\n",
    "        if k >= self._len - _list_lens[-1]:\n",
    "            return len(_list_lens) - 1, k + _list_lens[-1] - self._len\n",
    "        if self._rebuild:\n",
    "            self._fen_build()\n",
    "\n",
    "        _fen_tree = self._fen_tree\n",
    "        idx = -1\n",
    "        for d in reversed(range(len(_fen_tree).bit_length())):\n",
    "            right_idx = idx + (1 << d)\n",
    "            if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:\n",
    "                idx = right_idx\n",
    "                k -= _fen_tree[idx]\n",
    "        return idx + 1, k\n",
    "\n",
    "    def _delete(self, pos, idx):\n",
    "        \"\"\"Delete value at the given `(pos, idx)`.\"\"\"\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    "\n",
    "        self._len -= 1\n",
    "        self._fen_update(pos, -1)\n",
    "        del _lists[pos][idx]\n",
    "        _list_lens[pos] -= 1\n",
    "\n",
    "        if _list_lens[pos]:\n",
    "            _mins[pos] = _lists[pos][0]\n",
    "        else:\n",
    "            del _lists[pos]\n",
    "            del _list_lens[pos]\n",
    "            del _mins[pos]\n",
    "            self._rebuild = True\n",
    "\n",
    "    def _loc_left(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the first position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    "\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "\n",
    "        lo, pos = -1, len(_lists) - 1\n",
    "        while lo + 1 < pos:\n",
    "            mi = (lo + pos) >> 1\n",
    "            if value <= _mins[mi]:\n",
    "                pos = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        if pos and value <= _lists[pos - 1][-1]:\n",
    "            pos -= 1\n",
    "\n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value <= _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        return pos, idx\n",
    "\n",
    "    def _loc_right(self, value):\n",
    "        \"\"\"Return an index pair that corresponds to the last position of `value` in the sorted list.\"\"\"\n",
    "        if not self._len:\n",
    "            return 0, 0\n",
    "\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "\n",
    "        pos, hi = 0, len(_lists)\n",
    "        while pos + 1 < hi:\n",
    "            mi = (pos + hi) >> 1\n",
    "            if value < _mins[mi]:\n",
    "                hi = mi\n",
    "            else:\n",
    "                pos = mi\n",
    "\n",
    "        _list = _lists[pos]\n",
    "        lo, idx = -1, len(_list)\n",
    "        while lo + 1 < idx:\n",
    "            mi = (lo + idx) >> 1\n",
    "            if value < _list[mi]:\n",
    "                idx = mi\n",
    "            else:\n",
    "                lo = mi\n",
    "\n",
    "        return pos, idx\n",
    "\n",
    "    def add(self, value):\n",
    "        \"\"\"Add `value` to sorted list.\"\"\"\n",
    "        _load = self._load\n",
    "        _lists = self._lists\n",
    "        _mins = self._mins\n",
    "        _list_lens = self._list_lens\n",
    "\n",
    "        self._len += 1\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            self._fen_update(pos, 1)\n",
    "            _list = _lists[pos]\n",
    "            _list.insert(idx, value)\n",
    "            _list_lens[pos] += 1\n",
    "            _mins[pos] = _list[0]\n",
    "            if _load + _load < len(_list):\n",
    "                _lists.insert(pos + 1, _list[_load:])\n",
    "                _list_lens.insert(pos + 1, len(_list) - _load)\n",
    "                _mins.insert(pos + 1, _list[_load])\n",
    "                _list_lens[pos] = _load\n",
    "                del _list[_load:]\n",
    "                self._rebuild = True\n",
    "        else:\n",
    "            _lists.append([value])\n",
    "            _mins.append(value)\n",
    "            _list_lens.append(1)\n",
    "            self._rebuild = True\n",
    "\n",
    "    def discard(self, value):\n",
    "        \"\"\"Remove `value` from sorted list if it is a member.\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_right(value)\n",
    "            if idx and _lists[pos][idx - 1] == value:\n",
    "                self._delete(pos, idx - 1)\n",
    "\n",
    "    def remove(self, value):\n",
    "        \"\"\"Remove `value` from sorted list; `value` must be a member.\"\"\"\n",
    "        _len = self._len\n",
    "        self.discard(value)\n",
    "        if _len == self._len:\n",
    "            raise ValueError('{0!r} not in list'.format(value))\n",
    "\n",
    "    def pop(self, index=-1):\n",
    "        \"\"\"Remove and return value at `index` in sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        value = self._lists[pos][idx]\n",
    "        self._delete(pos, idx)\n",
    "        return value\n",
    "\n",
    "    def bisect_left(self, value):\n",
    "        \"\"\"Return the first index to insert `value` in the sorted list.\"\"\"\n",
    "        pos, idx = self._loc_left(value)\n",
    "        return self._fen_query(pos) + idx\n",
    "\n",
    "    def bisect_right(self, value):\n",
    "        \"\"\"Return the last index to insert `value` in the sorted list.\"\"\"\n",
    "        pos, idx = self._loc_right(value)\n",
    "        return self._fen_query(pos) + idx\n",
    "\n",
    "    def count(self, value):\n",
    "        \"\"\"Return number of occurrences of `value` in the sorted list.\"\"\"\n",
    "        return self.bisect_right(value) - self.bisect_left(value)\n",
    "\n",
    "    def __len__(self):\n",
    "        \"\"\"Return the size of the sorted list.\"\"\"\n",
    "        return self._len\n",
    "\n",
    "    def __getitem__(self, index):\n",
    "        \"\"\"Lookup value at `index` in sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        return self._lists[pos][idx]\n",
    "\n",
    "    def __delitem__(self, index):\n",
    "        \"\"\"Remove value at `index` from sorted list.\"\"\"\n",
    "        pos, idx = self._fen_findkth(self._len + index if index < 0 else index)\n",
    "        self._delete(pos, idx)\n",
    "\n",
    "    def __contains__(self, value):\n",
    "        \"\"\"Return true if `value` is an element of the sorted list.\"\"\"\n",
    "        _lists = self._lists\n",
    "        if _lists:\n",
    "            pos, idx = self._loc_left(value)\n",
    "            return idx < len(_lists[pos]) and _lists[pos][idx] == value\n",
    "        return False\n",
    "\n",
    "    def __iter__(self):\n",
    "        \"\"\"Return an iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in self._lists for value in _list)\n",
    "\n",
    "    def __reversed__(self):\n",
    "        \"\"\"Return a reverse iterator over the sorted list.\"\"\"\n",
    "        return (value for _list in reversed(self._lists) for value in reversed(_list))\n",
    "\n",
    "    def __repr__(self):\n",
    "        \"\"\"Return string representation of sorted list.\"\"\"\n",
    "        return 'SortedList({0})'.format(list(self))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://leetcode.cn/problems/sliding-window-median/solutions/589213/feng-xian-dui-chong-shuang-dui-dui-ding-hq1dt/?orderBy=hot\n",
    "# 记账，延迟删除，balance平衡因子\n",
    "\n",
    "# 你所说的\"在平衡过程中，正好移动的元素是要删除的元素“这件事情是不会发生的。如果需要进行平衡，需要满足两个条件。\n",
    "\n",
    "# balance=2，这意味着此次窗口滑动过程中，small堆比big堆多出来两个元素。这只能由：删除了big堆中的一个元素，并且向small堆中添加了一个元素。而对应的调整策略则是将small堆顶元素送给big堆：删掉的是big堆中的元素，转移的则是small堆中的元素，所以正好移动的元素不会是要删除的元素。\n",
    "\n",
    "# balance=-2，这意味着此次窗口滑动过程中，big堆比small堆多出来两个元素。这只能由：删除了small堆中的一个元素，并且向big堆中添加了一个元素。而对应的调整策略则是将big堆顶元素送给small堆：删掉的是small堆中的元素，转移的则是big堆中的元素，所以正好移动的元素不会是要删除的元素。\n",
    "\n",
    "# 综上所述，“平衡过程中，正好要移动的元素是要删除的元素”，这件事情是不会发生的。这也是双堆堆顶求中位数时候巧妙之所在。\n",
    "class Heap:\n",
    "    def __init__(self, name=\"min\"):\n",
    "        self.arr = []\n",
    "        self.f = lambda x: x if name==\"min\" else -x\n",
    "    def push(self, num):\n",
    "        heapq.heappush(self.arr, self.f(num))                   # 推入一个\n",
    "    def pop(self):\n",
    "        return self.f(heapq.heappop(self.arr))                  # 弹出堆顶\n",
    "    def top(self):\n",
    "        return self.f(self.arr[0])\n",
    "    def empty(self):\n",
    "        return len(self.arr) == 0\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        small = Heap(name=\"max\") # 较小数字部分使用大根堆\n",
    "        big = Heap(name=\"min\")   # 较大数字部分使用小根堆\n",
    "        get_mid = lambda x, y: x.top() if k % 2 else (x.top() + y.top()) / 2\n",
    "        mp = collections.defaultdict(int)\n",
    "        for i in range(k):\n",
    "            small.push(nums[i])\n",
    "        for i in range(k//2):\n",
    "            big.push(small.pop())\n",
    "        ans = [get_mid(small, big)]\n",
    "        for i in range(k, len(nums)):\n",
    "            balance = 0 # balance表示因本次窗口滑动导致small堆元素数目与big堆元素个数差值的增量\n",
    "            l, r = nums[i-k], nums[i]  # 将被删除的窗口最左元素和将被添加到窗口最右的元素\n",
    "            mp[l] += 1                 # 左窗口元素记账\n",
    "            if l <= small.top():\n",
    "                balance -= 1           # 较小数字堆需删除一个元素\n",
    "            else:\n",
    "                balance += 1           # 较大数字堆需删除一个元素\n",
    "            if r <= small.top():\n",
    "                balance += 1           # 较小数字堆添加一个元素\n",
    "                small.push(r)\n",
    "            else:\n",
    "                balance -= 1           # 较大数字堆添加一个元素\n",
    "                big.push(r)\n",
    "            \"\"\"\n",
    "            此时balance取值可能是:\n",
    "            balance | small | big  | 解释\n",
    "              0     | -1+1  |      | 较小数字堆删除一个元素添加一个元素，两边还是平衡的\n",
    "              0     |       | +1-1 | 较大数字堆删除一个元素添加一个元素，两边还是平衡的\n",
    "             -2     | -1    | -1   | 较小数字堆删除一个元素，较大数字堆添加一个元素，失衡\n",
    "              2     | +1    | +1   | 较大数字堆删除一个元素，较小数字堆添加一个元素，失衡\n",
    "            \"\"\"\n",
    "            # 较小数字堆挪一个给较大数字堆(3,3)->(4,2)->(3,3)或者(4,3)->(5,2)->(4,3)\n",
    "            if balance == 2:\n",
    "                big.push(small.pop())\n",
    "            # 较大数字堆挪一个给较小数字堆(3,3)->(2,4)->(3,3)或者(4,3)->(3,4)->(4,3)\n",
    "            if balance == -2:\n",
    "                small.push(big.pop())\n",
    "            # 重新达到平衡了,该看看堆顶是不是待删除元素了\n",
    "            while not small.empty() and mp[small.top()]:\n",
    "                mp[small.top()] -= 1\n",
    "                small.pop()\n",
    "            while not big.empty() and mp[big.top()]:\n",
    "                mp[big.top()] -= 1\n",
    "                big.pop()\n",
    "            # 为什么删除堆顶元素后不用重新平衡两边堆了呢？\n",
    "            ans.append(get_mid(small, big))\n",
    "        return ans\n",
    "\n",
    "# 作者：Hao Kun Yang\n",
    "# 链接：https://leetcode.cn/problems/sliding-window-median/solutions/589052/python-shuang-dui-shuang-ha-xi-dui-liang-jb34/\n",
    "# 缺点：将堆顶在窗口外的元素清除出去，耗时\n",
    "# class Solution:\n",
    "#     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "#         min_heap,max_heap = [],[]\n",
    "\n",
    "#         # 初始化\n",
    "#         for i in range(k):\n",
    "#             heapq.heappush(min_heap,(nums[i],i))\n",
    "#         for i in range(k//2):\n",
    "#             n,idx = heapq.heappop(min_heap)\n",
    "#             heapq.heappush(max_heap,(-n,idx))\n",
    "        \n",
    "#         res = [(min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0]\n",
    "        \n",
    "#         for i in range(k,len(nums)):\n",
    "#             # 如果新数字应该放到最大堆\n",
    "#             if nums[i] < min_heap[0][0]:\n",
    "#                 heapq.heappush(max_heap,(-nums[i],i))\n",
    "#                 # 如果要弹出的元素在最小堆中，调整\n",
    "#                 if nums[i-k] >= min_heap[0][0]:\n",
    "#                     n,idx = heapq.heappop(max_heap)\n",
    "#                     heapq.heappush(min_heap,(-n,idx))\n",
    "#             else:\n",
    "#                 heapq.heappush(min_heap,(nums[i],i))\n",
    "#                 # 如果要弹出的元素在最大堆中，调整\n",
    "#                 # 取等号是特殊情况\n",
    "#                 if nums[i-k] <= min_heap[0][0]:\n",
    "#                     n,idx = heapq.heappop(min_heap)\n",
    "#                     heapq.heappush(max_heap,(-n,idx))\n",
    "            \n",
    "#             # 将堆顶在窗口外的元素清除出去\n",
    "#             while min_heap and min_heap[0][1] <= i-k:\n",
    "#                 heapq.heappop(min_heap)\n",
    "#             while max_heap and max_heap[0][1] <= i-k:\n",
    "#                 heapq.heappop(max_heap)\n",
    "            \n",
    "#             # 添加答案\n",
    "#             res.append((min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0)\n",
    "            \n",
    "#         return res\n",
    "\n",
    "# 时间复杂度：O(nlogk)\n",
    "# class Solution:\n",
    "#     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "#         from sortedcontainers import SortedList\n",
    "\n",
    "#         def mid(sl):\n",
    "#             n = len(sl)\n",
    "#             p = n // 2\n",
    "#             if n % 2 == 0:\n",
    "#                 return (sl[p - 1] + sl[p]) / 2\n",
    "#             else:\n",
    "#                 return 1.0 * sl[p]\n",
    "\n",
    "#         sl = SortedList(nums[:k])\n",
    "\n",
    "#         n = len(nums)\n",
    "#         ans = [0] * (n - k + 1)\n",
    "#         ans[0] = mid(sl)\n",
    "\n",
    "#         for i in range(k, n):\n",
    "#             prev = nums[i - k]\n",
    "#             num = nums[i]\n",
    "#             sl.add(num)\n",
    "#             sl.remove(prev)\n",
    "#             ans[i - k + 1] = mid(sl)\n",
    "\n",
    "#         return ans\n",
    "\n",
    "# 时间复杂度：O(nk)，循环是O(n), 二分查找是O(log(k)), pop和insert是O(k) \n",
    "# python的list还是用数组实现的，所以插入和删除其实是O(k)的复杂度\n",
    "# import bisect\n",
    "# class Solution:\n",
    "#     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "#         # 对于数组长度的奇偶性无需判断，通用\n",
    "#         median = lambda a: (a[(len(a)-1)//2] + a[len(a)//2]) / 2\n",
    "#         a = sorted(nums[:k])\n",
    "#         res = [median(a)]\n",
    "#         for i, j in zip(nums[:-k], nums[k:]):\n",
    "#             a.pop(bisect.bisect_left(a, i))\n",
    "#             bisect.insort_left(a, j)\n",
    "#             res.append(median(a))\n",
    "#         return res\n",
    "\n",
    "# 作者：听听\n",
    "# 链接：https://leetcode.cn/problems/sliding-window-median/solutions/588891/python3-chao-xiang-xi-duo-jie-fa-bao-li-ga02a/\n",
    "\n",
    "# 作者：Lysias\n",
    "# 链接：https://leetcode.cn/problems/sliding-window-median/solutions/588901/huan-you-na-wei-xiao-huo-ban-mei-you-shi-v1xm/\n",
    "\n",
    "# https://leetcode.cn/problems/sliding-window-median/solutions/593533/ke-pu-yi-xia-chang-jian-jie-fa-de-shi-ji-kvt3/?orderBy=hot&languageTags=python3%2Cpython\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "from collections import defaultdict\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k:int):\n",
    "        self.small = list()\n",
    "        self.large = list()\n",
    "        self.delayed = defaultdict(int)\n",
    "        self.k = k\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "    def prune(self, heap:List[int]):\n",
    "        while heap:\n",
    "            top_num = heap[0]\n",
    "            if heap is self.small:\n",
    "                top_num = -top_num\n",
    "            if self.delayed[top_num]!=0:\n",
    "                heapq.heappop(heap)\n",
    "                self.delayed[top_num] -= 1\n",
    "            else:\n",
    "                break\n",
    "        pass\n",
    "\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize>self.largeSize+1:\n",
    "            heapq.heappush(self.large, -self.small[0])\n",
    "            heapq.heappop(self.small)\n",
    "            self.largeSize += 1\n",
    "            self.smallSize -= 1\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize<self.largeSize:\n",
    "            heapq.heappush(self.small, -self.large[0])\n",
    "            heapq.heappop(self.large)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "        pass\n",
    "\n",
    "    def insert(self, num:int):\n",
    "        if len(self.small)==0 or num<=-self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize+=1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize +=1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num:int):\n",
    "        self.delayed[num] += 1\n",
    "        if num<=-self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self):\n",
    "        return float(-self.small[0]) if self.k%2==1 else \\\n",
    "                (-self.small[0]+self.large[0])/2\n",
    "        pass\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for i in range(k):\n",
    "            dh.insert(nums[i])\n",
    "        res = [dh.getMedian()]\n",
    "        for i in range(k,len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i-k])\n",
    "            res.append(dh.getMedian())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "from collections import *\n",
    "class Solution: # 小数存放在大根堆hsmall,负数;大数放在小根堆hbig,正数\n",
    "    def medianSlidingWindow(self, nums, k):\n",
    "        hsmall=[-num for num in nums[:k]]   # 先取开头k个数建大根堆\n",
    "        heapify(hsmall)\n",
    "        hbig,res=[],[]\n",
    "        cnt=defaultdict(int)    # 对应的数需要删除的次数，也可以将(num,index)一起存入堆\n",
    "        for i in range(k//2):   # 取出其中k//2个数建小根堆\n",
    "            heappush(hbig,-heappop(hsmall))\n",
    "        balance=0   # 初始是平衡状态\n",
    "        if k%2: # 添加第一个滑动窗口结果\n",
    "            res.append(-hsmall[0])\n",
    "        else:\n",
    "            res.append((-hsmall[0]+hbig[0])/2)\n",
    "        for i,num in enumerate(nums[k:],k):\n",
    "            if num<=-hsmall[0]: # 将num根据大小插入小数大根堆或大数小根堆，并修改balance\n",
    "                heappush(hsmall,-num)\n",
    "                balance+=1\n",
    "            else:\n",
    "                heappush(hbig,num)\n",
    "                balance-=1\n",
    "            cnt[nums[i-k]]+=1   # 记账需要删除的数，并修改balance\n",
    "            if nums[i-k]<=-hsmall[0]:\n",
    "                balance-=1\n",
    "            else:\n",
    "                balance+=1\n",
    "            if balance<0:   # 重新平衡\n",
    "                heappush(hsmall,-heappop(hbig))\n",
    "            elif balance>0:\n",
    "                heappush(hbig,-heappop(hsmall))\n",
    "            balance=0\n",
    "            while hsmall and cnt[-hsmall[0]]>0: # 检查两个堆顶元素是不是应该删除的，注意顺序\n",
    "                cnt[-hsmall[0]]-=1   # 先检查hsmall,因为之前记账需要删除的数时,是<=-hsmall[0]\n",
    "                heappop(hsmall)\n",
    "            while hbig and cnt[hbig[0]]>0:\n",
    "                cnt[hbig[0]]-=1\n",
    "                heappop(hbig)\n",
    "            if k%2:\n",
    "                res.append(-hsmall[0])\n",
    "            else:\n",
    "                res.append((-hsmall[0]+hbig[0])/2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def median(self, heap_max, heap_min, k):\n",
    "        if k % 2 == 1:\n",
    "            return -heap_max[0]\n",
    "        else:\n",
    "            return (-heap_max[0] + heap_min[0]) / 2\n",
    "\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        heap_max, heap_min = [], []\n",
    "        removes = collections.Counter()\n",
    "\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap_max, -nums[i])\n",
    "        for i in range(k // 2):\n",
    "            heapq.heappush(heap_min, -heapq.heappop(heap_max))\n",
    "\n",
    "        res = [self.median(heap_max, heap_min, k)]\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            banlance = 0\n",
    "            left, right = i - k, i\n",
    "            removes[nums[left]] += 1\n",
    "            if heap_max and nums[left] <= -heap_max[0]:\n",
    "                banlance -= 1\n",
    "            else:\n",
    "                banlance += 1\n",
    "\n",
    "            if heap_max and nums[right] <= -heap_max[0]:\n",
    "                heapq.heappush(heap_max, -nums[i])\n",
    "                banlance += 1\n",
    "            else:\n",
    "                banlance -= 1\n",
    "                heapq.heappush(heap_min, nums[i])\n",
    "\n",
    "            if banlance == -2:\n",
    "                heapq.heappush(heap_max, -heapq.heappop(heap_min))\n",
    "            if banlance == 2:\n",
    "                heapq.heappush(heap_min, -heapq.heappop(heap_max))\n",
    "\n",
    "            while heap_max and removes[-heap_max[0]] > 0:\n",
    "                removes[-heapq.heappop(heap_max)] -= 1\n",
    "            while heap_min and removes[heap_min[0]] > 0:\n",
    "                removes[heapq.heappop(heap_min)] -= 1\n",
    "            res.append(self.median(heap_max, heap_min, k))\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "class Median:\n",
    "    def __init__(self):\n",
    "        # 保证大根堆比小根堆多一个数，或者相等\n",
    "        self.maxheap = [] # 大根堆，保存下半部分数据\n",
    "        self.minheap = [] # 小根堆，保存上本部分数据\n",
    "\n",
    "        self.minsize = 0\n",
    "        self.maxsize = 0\n",
    "\n",
    "        self.hashmap = defaultdict(int)\n",
    "\n",
    "    def insert(self,num):\n",
    "        minheap = self.minheap\n",
    "        maxheap = self.maxheap\n",
    "        if not maxheap or num <= -(maxheap[0]):\n",
    "            heapq.heappush(maxheap, -num)\n",
    "            self.maxsize += 1\n",
    "        else:\n",
    "            heapq.heappush(minheap, num)\n",
    "            self.minsize += 1\n",
    "        \n",
    "        if self.maxsize>self.minsize+1:\n",
    "            heapq.heappush(minheap, -heapq.heappop(maxheap))\n",
    "            self.minsize += 1\n",
    "            self.maxsize -= 1\n",
    "            self.prune(maxheap)\n",
    "        elif self.minsize>self.maxsize:\n",
    "            heapq.heappush(maxheap, -heapq.heappop(minheap))\n",
    "            self.minsize -= 1\n",
    "            self.maxsize += 1\n",
    "            self.prune(minheap)\n",
    "\n",
    "    def erase(self,num):\n",
    "        minheap = self.minheap\n",
    "        maxheap = self.maxheap\n",
    "        hashmap = self.hashmap\n",
    "        hashmap[num] += 1\n",
    "        if num<=-(maxheap[0]):\n",
    "            self.maxsize -= 1\n",
    "            if num==-maxheap[0]:\n",
    "                self.prune(maxheap)\n",
    "        else:\n",
    "            self.minsize -= 1\n",
    "            if num==minheap[0]:\n",
    "                self.prune(minheap)\n",
    "\n",
    "        if self.maxsize>self.minsize+1:\n",
    "            heapq.heappush(minheap, -heapq.heappop(maxheap))\n",
    "            self.minsize += 1\n",
    "            self.maxsize -= 1\n",
    "            self.prune(maxheap)\n",
    "        elif self.minsize>self.maxsize:\n",
    "            heapq.heappush(maxheap, -heapq.heappop(minheap))\n",
    "            self.minsize -= 1\n",
    "            self.maxsize += 1\n",
    "            self.prune(minheap)\n",
    "\n",
    "    def prune(self,heap):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.maxheap:\n",
    "                num = -num\n",
    "            if self.hashmap[num]>0:\n",
    "                self.hashmap[num] -=1\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "    def getMedian(self):\n",
    "        minheap = self.minheap\n",
    "        maxheap = self.maxheap\n",
    "        if self.maxsize == self.minsize:\n",
    "            return (minheap[0]-maxheap[0])/2\n",
    "        else:\n",
    "            return float(-maxheap[0])\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        median = Median()\n",
    "        i = 0\n",
    "        while i<k:\n",
    "            median.insert(nums[i])\n",
    "            i+=1\n",
    "        ans = [median.getMedian()]\n",
    "        while i<len(nums):\n",
    "            median.insert(nums[i])\n",
    "            median.erase(nums[i-k])\n",
    "            ans.append(median.getMedian())\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k: int):\n",
    "        self.small = []\n",
    "        self.large = []\n",
    "        self.delayed = collections.Counter()\n",
    "        self.k = k\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "    def prune(self, heap: List[int]):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.small:\n",
    "                num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0:\n",
    "                    del self.delayed[num]\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    def makeBalance(self):\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            heapq.heappush(self.large, -heapq.heappop(self.small))\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            heapq.heappush(self.small, -heapq.heappop(self.large))\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def insert(self, num: int):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num: int):\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self) -> float:\n",
    "        return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)\n",
    "        \n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i - k])\n",
    "            ans.append(dh.getMedian())\n",
    "        \n",
    "        return ans\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k: int):\n",
    "        # 大根堆，维护较小的一半元素，注意 python 没有大根堆，需要将所有元素取相反数并使用小根堆\n",
    "        self.small = list()\n",
    "        # 小根堆，维护较大的一半元素\n",
    "        self.large = list()\n",
    "        # 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数\n",
    "        self.delayed = collections.Counter()\n",
    "\n",
    "        self.k = k\n",
    "        # small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "\n",
    "    # 不断地弹出 heap 的堆顶元素，并且\b更新哈希表\n",
    "    def prune(self, heap: List[int]):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.small:\n",
    "                num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0:\n",
    "                    self.delayed.pop(num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    # 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            # small 比 large 元素多 2 个\n",
    "            heapq.heappush(self.large, -self.small[0])\n",
    "            heapq.heappop(self.small)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            # small 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            # large 比 small 元素多 1 个\n",
    "            heapq.heappush(self.small, -self.large[0])\n",
    "            heapq.heappop(self.large)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            # large 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def insert(self, num: int):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num: int):\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self) -> float:\n",
    "        return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)\n",
    "        \n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i - k])\n",
    "            ans.append(dh.getMedian())\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "#         n = len(nums)\n",
    "#         res = []\n",
    "        \n",
    "        \n",
    "#         def find_median(arr):\n",
    "#             min_heap = []\n",
    "#             max_heap = []\n",
    "         \n",
    "#             for i in arr:\n",
    "#                 if len(min_heap) != len(max_heap):\n",
    "#                     heappush(min_heap, i)\n",
    "#                     heappush(max_heap, - heappop(min_heap))\n",
    "#                 else:\n",
    "#                     heappush(max_heap, -i)\n",
    "#                     heappush(min_heap, -heappop(max_heap))\n",
    "#             # print(\"arr is {}\".format(arr))\n",
    "#             # print(\"min_heap is {}\".format(min_heap))\n",
    "#             # print(\"max_heap is {}\".format(max_heap))\n",
    "#             return min_heap[0] if len(min_heap) != len(max_heap) else (min_heap[0] - max_heap[0]) / 2\n",
    "            \n",
    "        \n",
    "#         for i in range(n - k + 1):\n",
    "#             tmp = nums[i: i + k]\n",
    "#             res.append(find_median(tmp))\n",
    "            \n",
    "                \n",
    "#         return res\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k: int):\n",
    "        # 大根堆，维护较小的一半元素，注意 python 没有大根堆，需要将所有元素取相反数并使用小根堆\n",
    "        self.small = list()\n",
    "        # 小根堆，维护较大的一半元素\n",
    "        self.large = list()\n",
    "        # 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数\n",
    "        self.delayed = collections.Counter()\n",
    "\n",
    "        self.k = k\n",
    "        # small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "\n",
    "    # 不断地弹出 heap 的堆顶元素，并且\b更新哈希表\n",
    "    def prune(self, heap: List[int]):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.small:\n",
    "                num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0:\n",
    "                    self.delayed.pop(num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    # 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            # small 比 large 元素多 2 个\n",
    "            heapq.heappush(self.large, -self.small[0])\n",
    "            heapq.heappop(self.small)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            # small 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            # large 比 small 元素多 1 个\n",
    "            heapq.heappush(self.small, -self.large[0])\n",
    "            heapq.heappop(self.large)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            # large 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def insert(self, num: int):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num: int):\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self) -> float:\n",
    "        return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)\n",
    "        \n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i - k])\n",
    "            ans.append(dh.getMedian())\n",
    "        \n",
    "        return ans\n",
    "    \n",
    "    \n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k: int):\n",
    "        self.small,self.large = [],[]\n",
    "        self.delayed = collections.Counter()\n",
    "        self.k = k\n",
    "        self.smallSize,self.largeSize = 0,0\n",
    "    def prune(self, heap: List[int]):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.small: num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0: self.delayed.pop(num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            heapq.heappush(self.large, -heapq.heappop(self.small))\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            heapq.heappush(self.small, -heapq.heappop(self.large))\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "    def insert(self, num: int):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "    def erase(self, num: int):\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]: self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]: self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "    def getMedian(self) -> float:\n",
    "        return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)        \n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i - k])\n",
    "            ans.append(dh.getMedian())        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "import collections\n",
    "from collections import defaultdict\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k:int):\n",
    "        self.small = list()\n",
    "        self.large = list()\n",
    "        self.delayed = defaultdict(int)\n",
    "        self.k = k\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "    def prune(self, heap:List[int]):\n",
    "        while heap:\n",
    "            top_num = heap[0]\n",
    "            if heap is self.small:\n",
    "                top_num = -top_num\n",
    "            if top_num in self.delayed:\n",
    "                self.delayed[top_num] -= 1\n",
    "                if self.delayed[top_num] == 0:\n",
    "                    self.delayed.pop(top_num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "\n",
    "            # if self.delayed[top_num]!=0:\n",
    "            #     heapq.heappop(heap)\n",
    "            #     self.delayed[top_num] -= 1\n",
    "            # else:\n",
    "            #     break\n",
    "        pass\n",
    "\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize>self.largeSize+1:\n",
    "            heapq.heappush(self.large, -self.small[0])\n",
    "            heapq.heappop(self.small)\n",
    "            self.largeSize += 1\n",
    "            self.smallSize -= 1\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize<self.largeSize:\n",
    "            heapq.heappush(self.small, -self.large[0])\n",
    "            heapq.heappop(self.large)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "        pass\n",
    "\n",
    "    def insert(self, num:int):\n",
    "        if len(self.small)==0 or num<=-self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize+=1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize +=1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num:int):\n",
    "        self.delayed[num] += 1\n",
    "        if num<=-self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self):\n",
    "        return float(-self.small[0]) if self.k%2==1 else \\\n",
    "                (-self.small[0]+self.large[0])/2\n",
    "        pass\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for i in range(k):\n",
    "            dh.insert(nums[i])\n",
    "        res = [dh.getMedian()]\n",
    "        for i in range(k,len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i-k])\n",
    "            res.append(dh.getMedian())\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "class DualHeap:\n",
    "    def __init__(self, k: int):\n",
    "        # 大根堆，维护较小的一半元素，注意 python 没有大根堆，需要将所有元素取相反数并使用小根堆\n",
    "        self.small = list()\n",
    "        # 小根堆，维护较大的一半元素\n",
    "        self.large = list()\n",
    "        # 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数\n",
    "        self.delayed = collections.Counter()\n",
    "\n",
    "        self.k = k\n",
    "        # small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "\n",
    "\n",
    "    # 不断地弹出 heap 的堆顶元素，并且\b更新哈希表\n",
    "    def prune(self, heap: List[int]):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.small:\n",
    "                num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0:\n",
    "                    self.delayed.pop(num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    # 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求\n",
    "    def makeBalance(self):\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            # small 比 large 元素多 2 个\n",
    "            heapq.heappush(self.large, -self.small[0])\n",
    "            heapq.heappop(self.small)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            # small 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            # large 比 small 元素多 1 个\n",
    "            heapq.heappush(self.small, -self.large[0])\n",
    "            heapq.heappop(self.large)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            # large 堆顶元素被移除，需要进行 prune\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def insert(self, num: int):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.large, num)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num: int):\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "    def getMedian(self) -> float:\n",
    "        return float(-self.small[0]) if self.k % 2 == 1 else (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k)\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)\n",
    "        \n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.erase(nums[i - k])\n",
    "            dh.insert(nums[i])\n",
    "            \n",
    "            ans.append(dh.getMedian())\n",
    "            #print(dh.small, dh.large)\n",
    "        \n",
    "        return ans\n",
    "'''\n",
    "\n",
    "#'''\n",
    "class MedianCaldulator:\n",
    "    def __init__(self):\n",
    "        # small 那一半\n",
    "        self.max_heap = []\n",
    "        # large 那一半\n",
    "        self.min_heap = []\n",
    "        self.max_heap_supposed_size = 0\n",
    "        self.min_heap_supposed_size = 0\n",
    "        self.delay_remove = defaultdict(int)\n",
    "    def insert(self, num):\n",
    "        # 判断 插入元素应该属于 small(max_heap) 还是 large(min_heap),然后插入进去\n",
    "        if (not self.max_heap and not self.min_heap) or\\\n",
    "                self.max_heap and num <= -self.max_heap[0]:\n",
    "            heapq.heappush(self.max_heap, -num)\n",
    "            self.max_heap_supposed_size += 1\n",
    "        else:\n",
    "            heapq.heappush(self.min_heap, num)\n",
    "            self.min_heap_supposed_size += 1\n",
    "        # 插入之后有可能两个 heap 不再平衡，需要 balance\n",
    "        self.balance()\n",
    "\n",
    "    # 调整 small(max_heap) 和 large(min_heap) 中的 supposed 元素个数，使得二者的元素(supposed而不是实际的)个数满足要求\n",
    "    def balance(self):\n",
    "        if self.max_heap_supposed_size < self.min_heap_supposed_size:\n",
    "            # large 比 small supposed 元素多 1 个\n",
    "            popped = heapq.heappop(self.min_heap)\n",
    "            self.min_heap_supposed_size -= 1\n",
    "            heapq.heappush(self.max_heap, -popped)\n",
    "            self.max_heap_supposed_size += 1\n",
    "            # large 堆顶元素被移除，变成 small 与 large supposed 元素个数相等，漏出了新的堆顶元素 ，需要进行 prune （不改变应有元素个数），使得堆顶元素不是待删除元素，那么求median时取的堆顶元素就是对的\n",
    "            self.prune(self.min_heap, False)\n",
    "        elif self.max_heap_supposed_size - self.min_heap_supposed_size > 1:\n",
    "            # small 比 large supposed 元素多 2 个\n",
    "            popped = heapq.heappop(self.max_heap)\n",
    "            self.max_heap_supposed_size -= 1\n",
    "            heapq.heappush(self.min_heap, -popped)\n",
    "            self.min_heap_supposed_size += 1\n",
    "            # small 堆顶元素被移除，变成 small 比 large 应有 元素多 1 个，漏出了新的堆顶元素 ，需要进行 prune （不改变应有元素个数），使得堆顶元素不是待删除元素，那么求median时取的堆顶元素就是对的\n",
    "            self.prune(self.max_heap)\n",
    "\n",
    "    def prune(self, heap, ismaxheap=True):\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if heap is self.max_heap:\n",
    "                num = -num\n",
    "            if num in self.delay_remove:\n",
    "                self.delay_remove[num] -= 1\n",
    "                if self.delay_remove[num] == 0:\n",
    "                    self.delay_remove.pop(num)\n",
    "                heapq.heappop(heap)\n",
    "            else:\n",
    "                break\n",
    "        '''\n",
    "        # 如果 堆顶元素 在delay_remove 中 不断地弹出 heap 的堆顶元素，并且更新哈希表： 这个操作并不改变 supposed size\n",
    "        if heap:\n",
    "            to_remove = -heap[0] if ismaxheap else heap[0]\n",
    "            while self.delay_remove.get(to_remove, 0) > 0:\n",
    "                heapq.heappop(heap)\n",
    "                self.delay_remove[to_remove] -= 1\n",
    "        '''\n",
    "\n",
    "    def remove(self, num):\n",
    "        # remove given num from heaps\n",
    "        self.delay_remove[num] += 1\n",
    "        # 如果num 大于或等于 large （min_heap）的 堆顶元素，说明其 一定在 large 中，否则在small 中\n",
    "        if num >= self.min_heap[0]:\n",
    "            self.min_heap_supposed_size -= 1\n",
    "            self.prune(self.min_heap, False)\n",
    "        else:\n",
    "            self.max_heap_supposed_size -= 1\n",
    "            self.prune(self.max_heap)\n",
    "        # supposed heap size 改变了，可能需要balance\n",
    "        self.balance()\n",
    "\n",
    "    def median(self):\n",
    "        if self.max_heap_supposed_size == self.min_heap_supposed_size:\n",
    "            return (-self.max_heap[0] + self.min_heap[0]) / 2\n",
    "        else:\n",
    "            return -self.max_heap[0]\n",
    "\n",
    "\n",
    "'''\n",
    "class MedianCaldulator:\n",
    "    def __init__(self):\n",
    "        self.max_heap = []\n",
    "        self.min_heap = []\n",
    "        self.max_heap_supposed_size = 0\n",
    "        self.min_heap_supposed_size = 0\n",
    "        self.delay_remove = defaultdict(int)\n",
    "    def insert(self, num):\n",
    "        # 判断 插入元素应该属于 small(max_heap) 还是 large(min_heap),然后插入进去\n",
    "        if (not self.max_heap and not self.min_heap) or\\\n",
    "                self.max_heap and num <= -self.max_heap[0]:\n",
    "            heapq.heappush(self.max_heap, -num)\n",
    "            self.max_heap_supposed_size += 1\n",
    "        else:\n",
    "            heapq.heappush(self.min_heap, num)\n",
    "            self.min_heap_supposed_size += 1\n",
    "        # 插入之后有可能两个 heap 不再平衡，需要 balance\n",
    "        self.balance()\n",
    "\n",
    "    # 调整 small(max_heap) 和 large(min_heap) 中的 supposed 元素个数，使得二者的元素(supposed而不是实际的)个数满足要求\n",
    "    def balance(self):\n",
    "        if self.max_heap_supposed_size < self.min_heap_supposed_size:\n",
    "            # large 比 small supposed 元素多 1 个\n",
    "            popped = heapq.heappop(self.min_heap)\n",
    "            self.min_heap_supposed_size -= 1\n",
    "            heapq.heappush(self.max_heap, -popped)\n",
    "            self.max_heap_supposed_size += 1\n",
    "            # large 堆顶元素被移除，变成 small 与 large supposed 元素个数相等，漏出了新的堆顶元素 ，需要进行 prune （不改变应有元素个数），使得堆顶元素不是待删除元素，那么求median时取的堆顶元素就是对的\n",
    "            #self.prune(self.min_heap, False)\n",
    "        elif self.max_heap_supposed_size - self.min_heap_supposed_size > 1:\n",
    "            # small 比 large supposed 元素多 2 个\n",
    "            popped = heapq.heappop(self.max_heap)\n",
    "            self.max_heap_supposed_size -= 1\n",
    "            heapq.heappush(self.min_heap, -popped)\n",
    "            self.min_heap_supposed_size += 1\n",
    "            # small 堆顶元素被移除，变成 small 比 large 应有 元素多 1 个，漏出了新的堆顶元素 ，需要进行 prune （不改变应有元素个数），使得堆顶元素不是待删除元素，那么求median时取的堆顶元素就是对的\n",
    "            #self.prune(self.max_heap)\n",
    "\n",
    "    def prune(self, heap, ismaxheap=True):\n",
    "        # 如果 堆顶元素 在delay_remove 中 不断地弹出 heap 的堆顶元素，并且更新哈希表： 这个操作并不改变 supposed size\n",
    "        if heap:\n",
    "            to_remove = -heap[0] if ismaxheap else heap[0]\n",
    "            while self.delay_remove.get(to_remove, 0) > 0:\n",
    "                heapq.heappop(heap)\n",
    "                self.delay_remove[to_remove] -= 1\n",
    "\n",
    "    def remove(self, num):\n",
    "        # remove given num from heaps\n",
    "        self.delay_remove[num] += 1\n",
    "        # 如果num 大于或等于 large （min_heap）的 堆顶元素，说明其 一定在 large 中，否则在small 中\n",
    "        if num >= self.min_heap[0]:\n",
    "            self.min_heap_supposed_size -= 1\n",
    "            self.min_heap.remove(num)\n",
    "            heapify(self.min_heap)\n",
    "            #self.prune(self.min_heap, False)\n",
    "        else:\n",
    "            self.max_heap_supposed_size -= 1\n",
    "            self.max_heap.remove(-num)\n",
    "            heapify(self.max_heap)\n",
    "            #self.prune(self.max_heap)\n",
    "        # supposed heap size 改变了，可能需要balance\n",
    "        self.balance()\n",
    "\n",
    "    def median(self):\n",
    "        if self.max_heap_supposed_size == self.min_heap_supposed_size:\n",
    "            return (-self.max_heap[0] + self.min_heap[0]) / 2\n",
    "        else:\n",
    "            return -self.max_heap[0]\n",
    "'''\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        mc = MedianCaldulator()\n",
    "        window = []\n",
    "        window_start = 0\n",
    "        n = len(nums)\n",
    "        end = n - k\n",
    "        res = []\n",
    "        while window_start <= end:\n",
    "            if window_start == 0:\n",
    "                for i in range(k):\n",
    "                    mc.insert(nums[i])\n",
    "            else:\n",
    "                window_end = window_start + k - 1\n",
    "                # 先insert 再 remove ，保证heap 不为空，比如nums=[1,2]，k=1\n",
    "                mc.insert(nums[window_end])\n",
    "                mc.remove(nums[window_start - 1])\n",
    "            #print(mc.max_heap, mc.min_heap)\n",
    "            #print(mc.delay_remove)\n",
    "            #print(mc.max_heap_supposed_size, mc.min_heap_supposed_size)\n",
    "            res.append(mc.median())\n",
    "            window_start += 1\n",
    "        #print(res)\n",
    "        return res\n",
    "#'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class DHeap:\n",
    "    def __init__(self, k):\n",
    "        self.minheap = []\n",
    "        self.maxheap = []\n",
    "        self.delay = Counter()\n",
    "        self.k = k\n",
    "        self.minHeapSize = 0\n",
    "        self.maxHeapSize = 0\n",
    "    \n",
    "    def insert(self, v):\n",
    "        if self.minHeapSize < self.maxHeapSize:\n",
    "            heapq.heappush(self.minheap, -heapq.heappushpop(self.maxheap, -v))\n",
    "            self.minHeapSize += 1\n",
    "        else:\n",
    "            heapq.heappush(self.maxheap, -heapq.heappushpop(self.minheap, v))\n",
    "            self.maxHeapSize += 1\n",
    "        # if self.minHeapSize > self.maxHeapSize:\n",
    "        #     print(\"???????\")\n",
    "        # self.balance()\n",
    "        self.prune(self.minheap)\n",
    "        self.prune(self.maxheap)\n",
    "\n",
    "    \n",
    "    def balance(self):\n",
    "        while self.maxHeapSize - self.minHeapSize > 1:\n",
    "            heapq.heappush(self.minheap, -heapq.heappop(self.maxheap))\n",
    "            self.maxHeapSize -= 1\n",
    "            self.minHeapSize += 1\n",
    "        while self.minHeapSize > self.maxHeapSize:\n",
    "            heapq.heappush(self.maxheap, -heapq.heappop(self.minheap))\n",
    "            self.maxHeapSize += 1\n",
    "            self.minHeapSize -= 1\n",
    "        self.prune(self.minheap)\n",
    "        self.prune(self.maxheap)\n",
    "\n",
    "    def prune(self, pq):\n",
    "        while pq:\n",
    "            num = pq[0] if pq != self.maxheap else -pq[0]\n",
    "            if num in self.delay:\n",
    "                self.delay[num] -= 1\n",
    "                heapq.heappop(pq)\n",
    "                if self.delay[num] == 0:\n",
    "                    self.delay.pop(num)\n",
    "            else:\n",
    "                break\n",
    "    \n",
    "    def remove(self, v):\n",
    "        self.delay[v] += 1\n",
    "        if v <= -self.maxheap[0]:\n",
    "            self.maxHeapSize -= 1\n",
    "            self.prune(self.maxheap)\n",
    "        else:\n",
    "            self.minHeapSize -= 1\n",
    "            self.prune(self.minheap)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        dpq = DHeap(k)\n",
    "        ret = []\n",
    "        for i in range(k-1):\n",
    "            dpq.insert(nums[i])\n",
    "            # print(dpq.minheap)\n",
    "            # print(dpq.maxheap)\n",
    "            # print(dpq.delay)\n",
    "            # print(dpq.minHeapSize, dpq.maxHeapSize)\n",
    "            # print(\"---------------\")\n",
    "\n",
    "        for i in range(k-1, n):\n",
    "            dpq.insert(nums[i])\n",
    "            # print(dpq.minheap)\n",
    "            # print(dpq.maxheap)\n",
    "            # print(dpq.delay)\n",
    "            # print(dpq.minHeapSize, dpq.maxHeapSize)\n",
    "            # print(\"---------------\")\n",
    "            median = -dpq.maxheap[0] if k%2 == 1 else (dpq.minheap[0]-dpq.maxheap[0])/2\n",
    "            ret.append(median)\n",
    "            dpq.remove(nums[i-k+1])\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def _push(heap, item, size):\n",
    "    if size == 0:\n",
    "        heap[0] = item\n",
    "        return size + 1\n",
    "\n",
    "    i = size\n",
    "    while i > 0:\n",
    "        parent = (i - 1) >> 1\n",
    "        if heap[parent] > item:\n",
    "            heap[i] = heap[parent]\n",
    "            i = parent\n",
    "        else:\n",
    "            break\n",
    "    heap[i] = item\n",
    "    return size + 1\n",
    "\n",
    "\n",
    "def _pop(heap, size):\n",
    "    if size == 0:\n",
    "        return None, size  # Heap is empty\n",
    "\n",
    "    root = heap[0]\n",
    "\n",
    "    last_element = heap[size - 1]\n",
    "    heap[0] = last_element\n",
    "    \n",
    "    size -= 1\n",
    "\n",
    "    i = 0\n",
    "    child = 2 * i + 1  # left child\n",
    "    while child < size:\n",
    "        if child + 1 < size and heap[child] > heap[child + 1]:\n",
    "            child += 1\n",
    "        if last_element > heap[child]:\n",
    "            heap[i] = heap[child]\n",
    "            i = child\n",
    "            child = 2 * i + 1\n",
    "        else:\n",
    "            break\n",
    "    heap[i] = last_element\n",
    "    return root, size\n",
    "\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, n):\n",
    "        self.small = [None] * n\n",
    "        self.large = [None] * n\n",
    "        self.delayed = collections.Counter()\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "        self.smallTrueSize = 0\n",
    "        self.largeTrueSize = 0\n",
    "        \n",
    "    def getMedian(self, k):\n",
    "        if k & 1:\n",
    "            return -self.small[0]\n",
    "        else:\n",
    "            return (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "    def prune(self, heap) -> None:\n",
    "        if heap is self.small:\n",
    "            size = self.smallTrueSize\n",
    "        else:\n",
    "            size = self.largeTrueSize\n",
    "        while size:\n",
    "            num = heap[0]\n",
    "            if heap is self.small:\n",
    "                num = -num\n",
    "            if num in self.delayed:\n",
    "                self.delayed[num] -= 1\n",
    "                if self.delayed[num] == 0:\n",
    "                    self.delayed.pop(num)\n",
    "                _, size = _pop(heap, size)\n",
    "            else:\n",
    "                break\n",
    "        if heap is self.small:\n",
    "            self.smallTrueSize = size\n",
    "        else:\n",
    "            self.largeTrueSize = size\n",
    "\n",
    "    def makeBalance(self) -> None:\n",
    "        if self.smallSize > self.largeSize + 1:\n",
    "            p, self.smallTrueSize = _pop(self.small, self.smallTrueSize)\n",
    "            self.largeTrueSize = _push(self.large, -p, self.largeTrueSize)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            self.prune(self.small)\n",
    "        elif self.smallSize < self.largeSize:\n",
    "            p, self.largeTrueSize = _pop(self.large, self.largeTrueSize)\n",
    "            self.smallTrueSize = _push(self.small, -p, self.smallTrueSize)\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def insert(self, num):\n",
    "        if (self.smallTrueSize == 0) or (num <= -self.small[0]):\n",
    "            self.smallTrueSize = _push(self.small, -num, self.smallTrueSize)\n",
    "            self.smallSize += 1\n",
    "        else:\n",
    "            self.largeTrueSize = _push(self.large, num, self.largeTrueSize)\n",
    "            self.largeSize += 1\n",
    "        self.makeBalance()\n",
    "\n",
    "    def erase(self, num) -> None:\n",
    "        if num not in self.delayed:\n",
    "            self.delayed[num] = 0\n",
    "        self.delayed[num] += 1\n",
    "        if num <= -self.small[0]:\n",
    "            self.smallSize -= 1\n",
    "            if num == -self.small[0]:\n",
    "                self.prune(self.small)\n",
    "        else:\n",
    "            self.largeSize -= 1\n",
    "            if num == self.large[0]:\n",
    "                self.prune(self.large)\n",
    "        self.makeBalance()\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums, k) :\n",
    "        dh = DualHeap(len(nums))\n",
    "        for num in nums[:k]:\n",
    "            dh.insert(num)\n",
    "        \n",
    "        ans = [dh.getMedian(k)]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.erase(nums[i - k])\n",
    "            ans.append(dh.getMedian(k))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 双优先队列 + 延迟删除\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k, nums)\n",
    "        res = []\n",
    "        i, n = k-1, len(nums)\n",
    "        while i < n:\n",
    "            dh.update(nums[i]) # 添加 nums[i]\n",
    "\n",
    "            res.append(dh.getMedian())\n",
    "\n",
    "            dh.delayDel(nums[i-k+1]) # 窗口滑动 当前窗口最后一个元素需要删除\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k, nums):\n",
    "        self.small = [] # 左半部分\n",
    "        self.large = [] # 右半部分 约定右半部分长度可以大 1\n",
    "        self.smallsize = 0 # 真实大小\n",
    "        self.largesize = 0 # 真实大小\n",
    "        self.delay = Counter() # 延迟删除\n",
    "        self.nums = nums\n",
    "        self.k = k\n",
    "\n",
    "        # init， 先将 k-1 个元素扔进堆中， 好让后面逻辑一致\n",
    "        i = 0\n",
    "        while i < k-1:\n",
    "            heappush(self.small, -nums[i])\n",
    "            heappush(self.large, -heappop(self.small))\n",
    "\n",
    "            # while和 if 都不影响 可以画出状态转移图 会发现 update 之后只会出现\n",
    "            # smallsize = largesize 或则smallsize + 1 = largesize\n",
    "            if len(self.large) > len(self.small) + 1: # 保证右半部分最多多 1\n",
    "                heappush(self.small, -heappop(self.large))\n",
    "            i += 1\n",
    "        self.smallsize = len(self.small)\n",
    "        self.largesize = len(self.large)\n",
    "\n",
    "    # 获得中位数\n",
    "    def getMedian(self) -> float:\n",
    "        if self.largesize == self.smallsize:\n",
    "            return -self.small[0] / 2.0 + self.large[0] / 2.0\n",
    "        return self.large[0]\n",
    "\n",
    "     # 添加值\n",
    "    def update(self, x :int) -> None:\n",
    "        heappush(self.small, -x)\n",
    "        heappush(self.large, -heappop(self.small))\n",
    "        self.largesize += 1\n",
    "        # 差值大于 1\n",
    "        if self.largesize > self.smallsize + 1:\n",
    "            heappush(self.small, -heappop(self.large))\n",
    "            self.largesize -= 1 \n",
    "            self.smallsize += 1\n",
    "        # 保证堆顶元素是合法的（未删除的）\n",
    "        self.adjust()\n",
    "    \n",
    "    # 延迟删除 （删除后， 最坏结果可能导致右半部分长度比左边长 2，但不要紧，在下一轮 update 中会恢复成差 1）\n",
    "    def delayDel(self, x: int) -> None:\n",
    "        self.delay[x] += 1\n",
    "        if self.small and x <= -self.small[0]:\n",
    "            self.smallsize -= 1\n",
    "        else:\n",
    "            self.largesize -= 1\n",
    "    \n",
    "    # 调整堆 使平衡 保证堆顶不是非法元素（已删除元素）\n",
    "    # 由于smallsize, largesize已经是真实的堆（删除元素后）的大小了。 所以在 adjust 的过程不需要更新这两个变量的值\n",
    "    def adjust(self) -> None:\n",
    "        while self.small and -self.small[0] in self.delay:\n",
    "            x = -heappop(self.small)\n",
    "            self.delay[x] -= 1\n",
    "            if self.delay[x] == 0:\n",
    "                del self.delay[x]\n",
    "        while self.large and self.large[0] in self.delay:\n",
    "            x = heappop(self.large)\n",
    "            self.delay[x] -= 1\n",
    "            if self.delay[x] == 0:\n",
    "                del self.delay[x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        small = [] # 左半部分大顶堆 \n",
    "        large = [] # 右半部分小顶堆 # 规定右边允许+1\n",
    "        smallsize = 0 # 真实长度\n",
    "        largesize = 0 # 真实长度\n",
    "        delay = Counter() # 延迟删除：要删除的元素不一定在堆顶 下次遇到了再删除\n",
    "\n",
    "        # 获得中位数\n",
    "        def getMedian() -> float:\n",
    "            if largesize == smallsize:\n",
    "                return -small[0] / 2.0 + large[0] / 2.0\n",
    "            return large[0]\n",
    "        \n",
    "        # 添加值\n",
    "        def update(x :int) -> None:\n",
    "            nonlocal largesize, smallsize\n",
    "            heappush(small, -x)\n",
    "            heappush(large, -heappop(small))\n",
    "            largesize += 1\n",
    "            # 差值大于 1\n",
    "            while largesize > smallsize + 1:\n",
    "                heappush(small, -heappop(large))\n",
    "                largesize -= 1 \n",
    "                smallsize += 1\n",
    "            adjust()\n",
    "        \n",
    "        # 删除\n",
    "        def delayDel(x: int) -> None:\n",
    "            nonlocal largesize, smallsize\n",
    "            delay[x] += 1\n",
    "            if small and x <= -small[0]:\n",
    "                smallsize -= 1\n",
    "            else:\n",
    "                largesize -= 1\n",
    "            adjust()\n",
    "        \n",
    "        # 调整堆 使平衡 保证堆顶不是要删除的元素 使 getMedian() 简单\n",
    "        def adjust() -> None:\n",
    "            # print(\"adjust, small: %s\" % small)\n",
    "            while small and -small[0] in delay:\n",
    "                x = -heappop(small)\n",
    "                delay[x] -= 1\n",
    "                if delay[x] == 0:\n",
    "                    del delay[x]\n",
    "            while large and large[0] in delay:\n",
    "                x = heappop(large)\n",
    "                delay[x] -= 1\n",
    "                if delay[x] == 0:\n",
    "                    del delay[x]\n",
    "            \n",
    "        i = 0\n",
    "        while i < k-1:\n",
    "            heappush(small, -nums[i])\n",
    "            heappush(large, -heappop(small))\n",
    "            if len(large) > len(small) + 1:\n",
    "                heappush(small, -heappop(large))\n",
    "            i += 1\n",
    "        smallsize = len(small)\n",
    "        largesize = len(large)\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        while i < n:\n",
    "            update(nums[i])\n",
    "\n",
    "            res.append(getMedian())\n",
    "\n",
    "            delayDel(nums[i-k+1])\n",
    "            \n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        small = [] # 左半部分大顶堆 \n",
    "        large = [] # 右半部分小顶堆 # 规定右边允许+1\n",
    "        smallsize = 0 # 真实长度\n",
    "        largesize = 0 # 真实长度\n",
    "        delay = Counter() # 延迟删除：要删除的元素不一定在堆顶 下次遇到了再删除\n",
    "\n",
    "        # 获得中位数\n",
    "        def getMedian() -> float:\n",
    "            if largesize == smallsize:\n",
    "                return -small[0] / 2.0 + large[0] / 2.0\n",
    "            return large[0]\n",
    "        \n",
    "        # 添加值\n",
    "        def update(x :int) -> None:\n",
    "            nonlocal largesize, smallsize\n",
    "            heappush(small, -x)\n",
    "            heappush(large, -heappop(small))\n",
    "            largesize += 1\n",
    "            # 差值大于 1\n",
    "            if largesize > smallsize + 1:\n",
    "                heappush(small, -heappop(large))\n",
    "                largesize -= 1 \n",
    "                smallsize += 1\n",
    "            adjust()\n",
    "        \n",
    "        # 删除\n",
    "        def delayDel(x: int) -> None:\n",
    "            nonlocal largesize, smallsize\n",
    "            delay[x] += 1\n",
    "            if small and x <= -small[0]:\n",
    "                smallsize -= 1\n",
    "            else:\n",
    "                largesize -= 1\n",
    "            adjust()\n",
    "        \n",
    "        # 调整堆 使平衡 保证堆顶不是要删除的元素 使 getMedian() 简单\n",
    "        def adjust() -> None:\n",
    "            # print(\"adjust, small: %s\" % small)\n",
    "            while small and -small[0] in delay:\n",
    "                x = -heappop(small)\n",
    "                delay[x] -= 1\n",
    "                if delay[x] == 0:\n",
    "                    del delay[x]\n",
    "            while large and large[0] in delay:\n",
    "                x = heappop(large)\n",
    "                delay[x] -= 1\n",
    "                if delay[x] == 0:\n",
    "                    del delay[x]\n",
    "            \n",
    "        i = 0\n",
    "        while i < k-1:\n",
    "            heappush(small, -nums[i])\n",
    "            heappush(large, -heappop(small))\n",
    "            if len(large) > len(small) + 1:\n",
    "                heappush(small, -heappop(large))\n",
    "            i += 1\n",
    "        smallsize = len(small)\n",
    "        largesize = len(large)\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        while i < n:\n",
    "            update(nums[i])\n",
    "\n",
    "            res.append(getMedian())\n",
    "\n",
    "            delayDel(nums[i-k+1])\n",
    "\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self) -> None:\n",
    "        self.leftMaxHeap = []\n",
    "        self.rightMinHeap = []\n",
    "        self.toBeRemoved = collections.Counter()\n",
    "        self.m = 0  # size of left max-heap\n",
    "        self.n = 0  # size of right max-heap\n",
    "\n",
    "    def add(self, num: int) -> None:\n",
    "        \"\"\"O(logk) add a number to one of the dual heaps\"\"\"\n",
    "        if not self.leftMaxHeap or num <= -self.leftMaxHeap[0]:\n",
    "            heappush(self.leftMaxHeap, -num)\n",
    "            self.m += 1\n",
    "        else:\n",
    "            heappush(self.rightMinHeap, num)\n",
    "            self.n += 1\n",
    "        self.balance()\n",
    "\n",
    "    def remove(self, num: int) -> None:\n",
    "        \"\"\"O(logk) remove a number from one of the dual heaps\"\"\"\n",
    "        self.toBeRemoved[num] += 1\n",
    "\n",
    "        if num <= -self.leftMaxHeap[0]:\n",
    "            self.m -= 1\n",
    "            if num == -self.leftMaxHeap[0]:\n",
    "                self.lazyDelete(self.leftMaxHeap, 'leftMaxHeap')\n",
    "        else:\n",
    "            self.n -= 1\n",
    "            if num == self.rightMinHeap[0]:\n",
    "                self.lazyDelete(self.rightMinHeap, 'rightMinHeap')\n",
    "        self.balance()\n",
    "\n",
    "    def lazyDelete(self, heap: List[int], type: str) -> None:\n",
    "        while heap:\n",
    "            num = heap[0]\n",
    "            if type == 'leftMaxHeap':\n",
    "                num = -num \n",
    "            if num in self.toBeRemoved:\n",
    "                self.toBeRemoved[num] -= 1\n",
    "                if self.toBeRemoved[num] == 0:\n",
    "                    self.toBeRemoved.pop(num)\n",
    "                heappop(heap)\n",
    "            else:\n",
    "                break \n",
    "\n",
    "    def balance(self) -> None:\n",
    "        \"\"\"O(logk) maintain length of dual heaps:\n",
    "            k is even: len(leftMaxHeap) = len(rightMinHeap)\n",
    "            k is odd: len(leftMaxHeap) = len(rightMinHeap) + 1\n",
    "        \"\"\"\n",
    "        while self.n > self.m:\n",
    "            heappush(self.leftMaxHeap, -heappop(self.rightMinHeap))\n",
    "            self.m += 1\n",
    "            self.n -= 1\n",
    "            self.lazyDelete(self.rightMinHeap, 'rightMinHeap')\n",
    "        while self.m > self.n + 1:\n",
    "            heappush(self.rightMinHeap, -heappop(self.leftMaxHeap))\n",
    "            self.m -= 1\n",
    "            self.n += 1\n",
    "            self.lazyDelete(self.leftMaxHeap, 'leftMaxHeap')\n",
    "\n",
    "\n",
    "    def median(self, k: int) -> float:\n",
    "        if k % 2:\n",
    "            return -self.leftMaxHeap[0]\n",
    "        else:\n",
    "            return (-self.leftMaxHeap[0] + self.rightMinHeap[0])/2\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[int]:\n",
    "        db = DualHeap()\n",
    "        # O(klogk)\n",
    "        for num in nums[:k]:\n",
    "            db.add(num)\n",
    "\n",
    "        ans = [db.median(k)]\n",
    "\n",
    "        for num1, num2 in zip(nums[:-k], nums[k:]):  # O(n-k)\n",
    "            db.add(num2)                # O(logk)\n",
    "            db.remove(num1)             # O(logk)\n",
    "            ans.append(db.median(k))        # O(1)\n",
    "\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DualHeap(k, nums)\n",
    "        res = []\n",
    "        i, n = k-1, len(nums)\n",
    "        while i < n:\n",
    "            dh.update(nums[i]) \n",
    "\n",
    "            res.append(dh.getMedian())\n",
    "\n",
    "            dh.delayDel(nums[i-k+1])\n",
    "\n",
    "            i += 1\n",
    "        return res\n",
    "\n",
    "class DualHeap:\n",
    "    def __init__(self, k, nums):\n",
    "        self.small = [] # 左半部分\n",
    "        self.large = [] # 右半部分\n",
    "        self.smallsize = 0 # 暂时大小\n",
    "        self.largesize = 0 # 真实大小\n",
    "        self.delay = Counter() # 延迟删除\n",
    "        self.nums = nums\n",
    "        self.k = k\n",
    "\n",
    "        # init\n",
    "        i = 0\n",
    "        while i < k-1:\n",
    "            heappush(self.small, -nums[i])\n",
    "            heappush(self.large, -heappop(self.small))\n",
    "            if len(self.large) > len(self.small) + 1:\n",
    "                heappush(self.small, -heappop(self.large))\n",
    "            i += 1\n",
    "        self.smallsize = len(self.small)\n",
    "        self.largesize = len(self.large)\n",
    "\n",
    "\n",
    "    def getMedian(self) -> float:\n",
    "        if self.largesize == self.smallsize:\n",
    "            return -self.small[0] / 2.0 + self.large[0] / 2.0\n",
    "        return self.large[0]\n",
    "\n",
    "     # 添加值\n",
    "    def update(self, x :int) -> None:\n",
    "        heappush(self.small, -x)\n",
    "        heappush(self.large, -heappop(self.small))\n",
    "        self.largesize += 1\n",
    "        # 差值大于 1\n",
    "        if self.largesize > self.smallsize + 1:\n",
    "            heappush(self.small, -heappop(self.large))\n",
    "            self.largesize -= 1 \n",
    "            self.smallsize += 1\n",
    "        self.adjust()\n",
    "    \n",
    "    def delayDel(self, x: int) -> None:\n",
    "        self.delay[x] += 1\n",
    "        if self.small and x <= -self.small[0]:\n",
    "            self.smallsize -= 1\n",
    "        else:\n",
    "            self.largesize -= 1\n",
    "        self.adjust()\n",
    "    \n",
    "    # 调整堆 使平衡 保证堆顶不是要删除的元素 使 getMedian() 简单\n",
    "    def adjust(self) -> None:\n",
    "        while self.small and -self.small[0] in self.delay:\n",
    "            x = -heappop(self.small)\n",
    "            self.delay[x] -= 1\n",
    "            if self.delay[x] == 0:\n",
    "                del self.delay[x]\n",
    "        while self.large and self.large[0] in self.delay:\n",
    "            x = heappop(self.large)\n",
    "            self.delay[x] -= 1\n",
    "            if self.delay[x] == 0:\n",
    "                del self.delay[x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        l, r = 0, 0\n",
    "        median = Median()\n",
    "        res = []\n",
    "        while r < len(nums):\n",
    "            while r < len(nums) and r - l < k:\n",
    "                median.add(nums[r])\n",
    "                r += 1\n",
    "            # print(median.h1)\n",
    "            # print(median.h2)\n",
    "            # print(median.cnt1)\n",
    "            # print(median.cnt2)\n",
    "            # print(median.delete)\n",
    "            res.append(median.query())\n",
    "            median.remove(nums[l])\n",
    "            l += 1\n",
    "        return res\n",
    "\n",
    "class Median:\n",
    "    def __init__(self):\n",
    "        self.size = 0\n",
    "        self.h1 = []\n",
    "        self.h2 = []\n",
    "        self.cnt1 = 0\n",
    "        self.cnt2 = 0\n",
    "        self.delete = defaultdict(int)\n",
    "    def modify(self):\n",
    "        while self.cnt1 > 0 and self.delete[-self.h1[0]] > 0:\n",
    "            x = -heapq.heappop(self.h1)\n",
    "            self.cnt1 -= 1\n",
    "            self.delete[x] -= 1\n",
    "        while self.cnt2 > 0 and self.delete[self.h2[0]] > 0:\n",
    "            x = heapq.heappop(self.h2)\n",
    "            self.cnt2 -= 1\n",
    "            self.delete[x] -= 1\n",
    "        while len(self.h1) - self.cnt1 > len(self.h2) - self.cnt2 + 1:\n",
    "            x = -heapq.heappop(self.h1)\n",
    "            heapq.heappush(self.h2, x)\n",
    "        while len(self.h1) - self.cnt1 < len(self.h2) - self.cnt2:\n",
    "            x = heapq.heappop(self.h2)\n",
    "            heapq.heappush(self.h1, -x)\n",
    "        while self.cnt1 > 0 and self.delete[-self.h1[0]] > 0:\n",
    "            x = -heapq.heappop(self.h1)\n",
    "            self.cnt1 -= 1\n",
    "            self.delete[x] -= 1\n",
    "        while self.cnt2 > 0 and self.delete[self.h2[0]] > 0:\n",
    "            x = heapq.heappop(self.h2)\n",
    "            self.cnt2 -= 1\n",
    "            self.delete[x] -= 1\n",
    "    def add(self, x):\n",
    "        if not self.h1 or x <= -self.h1[0]:\n",
    "            heapq.heappush(self.h1, -x)\n",
    "        else:\n",
    "            heapq.heappush(self.h2, x)\n",
    "        self.modify()\n",
    "    def remove(self, x):\n",
    "        if not self.h1:\n",
    "            return\n",
    "        if x == -self.h1[0]:\n",
    "            heapq.heappop(self.h1)\n",
    "        elif x < -self.h1[0]:\n",
    "            self.delete[x] += 1\n",
    "            self.cnt1 += 1\n",
    "        elif self.h2:\n",
    "            if x == self.h2[0]:\n",
    "                heapq.heappop(self.h2)\n",
    "            elif x > self.h2[0]:\n",
    "                self.delete[x] += 1\n",
    "                self.cnt2 += 1\n",
    "        self.modify()\n",
    "    def query(self):\n",
    "        if len(self.h1) - self.cnt1 == len(self.h2) - self.cnt2:\n",
    "            return (-self.h1[0] + self.h2[0]) / 2\n",
    "        else:\n",
    "            return -self.h1[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DoubleHeap:\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "        self.small = list()\n",
    "        self.large = list()\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "        self.delay = collections.Counter()\n",
    "    \n",
    "    def insert(self, num):\n",
    "        if not self.small:\n",
    "            self.smallSize += 1\n",
    "            heapq.heappush(self.small, -num)\n",
    "            return \n",
    "        if num <= -self.small[0]:\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.smallSize += 1\n",
    "            self.makebalance()\n",
    "            return\n",
    "        self.largeSize += 1\n",
    "        heapq.heappush(self.large, num)\n",
    "        self.makebalance()\n",
    "\n",
    "    def makebalance(self):\n",
    "        if self.smallSize - self.largeSize >= 2:\n",
    "            heapq.heappush(self.large, -heapq.heappop(self.small))\n",
    "            self.prune(self.small)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            return \n",
    "        if self.largeSize > self.smallSize:\n",
    "            heapq.heappush(self.small, -heapq.heappop(self.large))\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def delete(self, num):\n",
    "        if num <= -self.small[0]:\n",
    "            self.delay[-num] += 1\n",
    "            self.smallSize -= 1\n",
    "            self.prune(self.small)\n",
    "        else:\n",
    "            self.delay[num] += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "        self.makebalance()\n",
    "\n",
    "    def prune(self,h):\n",
    "        while h:\n",
    "            if self.delay[h[0]] < 1:\n",
    "                return\n",
    "            self.delay[h[0]] -= 1   \n",
    "            heapq.heappop(h)    \n",
    "\n",
    "    def getMedian(self):\n",
    "        if self.k % 2 == 1:\n",
    "            return -self.small[0]      \n",
    "        return (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DoubleHeap(k)\n",
    "        for v in nums[:k]:\n",
    "            dh.insert(v)\n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.delete(nums[i-k])\n",
    "            ans.append(dh.getMedian())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        from numpy import median\n",
    "        return [median(nums[i:i+k]) for i in range(len(nums)-k+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DoubleHeap:\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "        self.small = list()\n",
    "        self.large = list()\n",
    "        self.smallSize = 0\n",
    "        self.largeSize = 0\n",
    "        self.delay = collections.Counter()\n",
    "    \n",
    "    def insert(self, num):\n",
    "        if not self.small or num <= -self.small[0]:\n",
    "            self.smallSize += 1\n",
    "            heapq.heappush(self.small, -num)\n",
    "            self.makebalance()\n",
    "            return\n",
    "        self.largeSize += 1\n",
    "        heapq.heappush(self.large, num)\n",
    "        self.makebalance()\n",
    "\n",
    "    def makebalance(self):\n",
    "        if self.smallSize - self.largeSize >= 2:\n",
    "            heapq.heappush(self.large, -heapq.heappop(self.small))\n",
    "            self.prune(self.small)\n",
    "            self.smallSize -= 1\n",
    "            self.largeSize += 1\n",
    "            return \n",
    "        if self.largeSize > self.smallSize:\n",
    "            heapq.heappush(self.small, -heapq.heappop(self.large))\n",
    "            self.smallSize += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "\n",
    "    def delete(self, num):\n",
    "        if num <= -self.small[0]:\n",
    "            self.delay[-num] += 1\n",
    "            self.smallSize -= 1\n",
    "            self.prune(self.small)\n",
    "        else:\n",
    "            self.delay[num] += 1\n",
    "            self.largeSize -= 1\n",
    "            self.prune(self.large)\n",
    "        self.makebalance()\n",
    "\n",
    "    def prune(self,h):\n",
    "        while h:\n",
    "            if self.delay[h[0]] < 1:\n",
    "                return\n",
    "            self.delay[h[0]] -= 1   \n",
    "            heapq.heappop(h)    \n",
    "\n",
    "    def getMedian(self):\n",
    "        if self.k % 2 == 1:\n",
    "            return -self.small[0]      \n",
    "        return (-self.small[0] + self.large[0]) / 2\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        dh = DoubleHeap(k)\n",
    "        for v in nums[:k]:\n",
    "            dh.insert(v)\n",
    "        ans = [dh.getMedian()]\n",
    "        for i in range(k, len(nums)):\n",
    "            dh.insert(nums[i])\n",
    "            dh.delete(nums[i-k])\n",
    "            ans.append(dh.getMedian())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        from numpy import median\n",
    "        return [median(nums[i:i+k]) for i in range(len(nums)-k+1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        hp1, hp2 = [], []\n",
    "        total1, total2 = 0, 0\n",
    "        tag1, tag2 = {}, {}\n",
    "        ans = []\n",
    "        l = 0\n",
    "        for r, i in enumerate(nums):\n",
    "            if r - l + 1 > k:\n",
    "                n = nums[l]\n",
    "                if n in tag1:\n",
    "                    tag1[n] -= 1\n",
    "                    total1 -= 1\n",
    "                    if not tag1[n]:\n",
    "                        del tag1[n]\n",
    "                else:\n",
    "                    tag2[n] -= 1\n",
    "                    total2 -= 1\n",
    "                    if not tag2[n]:\n",
    "                        del tag2[n]\n",
    "                l += 1\n",
    "            if not total1:\n",
    "                hp1.append(-i)\n",
    "                tag1[i] = 1\n",
    "                total1 += 1\n",
    "            else:\n",
    "                if total1 > total2:\n",
    "                    t1 = 0\n",
    "                    while hp1:\n",
    "                        t1 = -heapq.heappop(hp1)\n",
    "                        if t1 in tag1:\n",
    "                            tag1[t1] -= 1\n",
    "                            total1 -= 1\n",
    "                            if not tag1[t1]:\n",
    "                                del tag1[t1]\n",
    "                            break\n",
    "                    if t1 <= i:\n",
    "                        heapq.heappush(hp1, -t1)\n",
    "                        if t1 not in tag1:\n",
    "                            tag1[t1] = 0\n",
    "                        tag1[t1] += 1\n",
    "                        total1 += 1\n",
    "                        heapq.heappush(hp2, i)\n",
    "                        if i not in tag2:\n",
    "                            tag2[i] = 0\n",
    "                        tag2[i] += 1\n",
    "                        total2 += 1\n",
    "                    else:\n",
    "                        heapq.heappush(hp2, t1)\n",
    "                        if t1 not in tag2:\n",
    "                            tag2[t1] = 0\n",
    "                        tag2[t1] += 1\n",
    "                        total2 += 1\n",
    "                        heapq.heappush(hp1, -i)\n",
    "                        if i not in tag1:\n",
    "                            tag1[i] = 0\n",
    "                        tag1[i] += 1\n",
    "                        total1 += 1\n",
    "                else:\n",
    "                    t2 = 0\n",
    "                    while hp2:\n",
    "                        t2 = heapq.heappop(hp2)\n",
    "                        if t2 in tag2:\n",
    "                            tag2[t2] -= 1\n",
    "                            total2 -= 1\n",
    "                            if not tag2[t2]:\n",
    "                                del tag2[t2]\n",
    "                            break\n",
    "                    if t2 <= i:\n",
    "                        heapq.heappush(hp2, i)\n",
    "                        if i not in tag2:\n",
    "                            tag2[i] = 0\n",
    "                        tag2[i] += 1\n",
    "                        total2 += 1\n",
    "                        heapq.heappush(hp1, -t2)\n",
    "                        if t2 not in tag1:\n",
    "                            tag1[t2] = 0\n",
    "                        tag1[t2] += 1\n",
    "                        total1 += 1\n",
    "                    else:\n",
    "                        heapq.heappush(hp2, t2)\n",
    "                        if t2 not in tag2:\n",
    "                            tag2[t2] = 0\n",
    "                        tag2[t2] += 1\n",
    "                        total2 += 1\n",
    "                        heapq.heappush(hp1, -i)\n",
    "                        if i not in tag1:\n",
    "                            tag1[i] = 0\n",
    "                        tag1[i] += 1\n",
    "                        total1 += 1\n",
    "            if r - l + 1 == k:\n",
    "                while hp1 and -hp1[0] not in tag1:\n",
    "                    heapq.heappop(hp1)\n",
    "                while hp2 and hp2[0] not in tag2:\n",
    "                    heapq.heappop(hp2)\n",
    "                if k % 2 == 0:\n",
    "                    ans.append((-hp1[0] + hp2[0]) / 2)\n",
    "                else:\n",
    "                    ans.append(-hp1[0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        return [np.median(nums[i:i+k]) for i in range(len(nums)-k+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "#import statistics # python3的内置函数\n",
    "class Solution: ##无脑暴力解法\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        i,j,n=0,k,len(nums)\n",
    "        res=[]\n",
    "        while j<=n:\n",
    "            res.append(np.median(nums[i:j]))\n",
    "            i+=1\n",
    "            j+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        heap_small = []\n",
    "        heap_large = nums[:k][:]\n",
    "        heapq.heapify(heap_large)\n",
    "        for _ in range(k>>1):\n",
    "            heapq.heappush(heap_small, -heapq.heappop(heap_large))\n",
    "        ans = [heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2]\n",
    "\n",
    "        large_size = small_size = 0\n",
    "        del_cnts = collections.defaultdict(int)\n",
    "\n",
    "        def clear():\n",
    "            while heap_large and del_cnts[heap_large[0]]:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                del_cnts[num] -= 1\n",
    "            while heap_small and del_cnts[-heap_small[0]]:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                del_cnts[-num] -= 1\n",
    "\n",
    "        def balance():\n",
    "            nonlocal large_size, small_size\n",
    "            clear()\n",
    "            if large_size > small_size+1:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                heapq.heappush(heap_small, -num)\n",
    "                large_size -= 1\n",
    "                small_size += 1\n",
    "            elif large_size < small_size:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                heapq.heappush(heap_large, -num)\n",
    "                large_size += 1\n",
    "                small_size -= 1\n",
    "            clear()\n",
    "\n",
    "        \n",
    "        for i in range(k, n):\n",
    "            add_num = nums[i]\n",
    "            del_num = nums[i-k]\n",
    "            if add_num == nums[i-k]:\n",
    "                ans.append(ans[-1])\n",
    "            else:\n",
    "                if not heap_large or add_num >= heap_large[0]:\n",
    "                    large_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_large, add_num)\n",
    "                else:\n",
    "                    small_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_small, -add_num)\n",
    "\n",
    "                del_cnts[del_num] += 1\n",
    "                if del_num >= heap_large[0]:\n",
    "                    large_size -= 1\n",
    "                else:\n",
    "                    small_size -= 1\n",
    "                balance()\n",
    "                if i>=k-1:\n",
    "                    ans.append(heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        heap_small = []\n",
    "        heap_large = nums[:k][:]\n",
    "        heapq.heapify(heap_large)\n",
    "        for _ in range(k>>1):\n",
    "            heapq.heappush(heap_small, -heapq.heappop(heap_large))\n",
    "        ans = [heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2]\n",
    "\n",
    "        balance = 0\n",
    "        del_cnts = collections.defaultdict(int)\n",
    "\n",
    "        def clear():\n",
    "            while heap_large and del_cnts[heap_large[0]]:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                del_cnts[num] -= 1\n",
    "            while heap_small and del_cnts[-heap_small[0]]:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                del_cnts[-num] -= 1\n",
    "\n",
    "        def balance_heap():\n",
    "            nonlocal balance\n",
    "            clear()\n",
    "            if balance > 0:\n",
    "                heapq.heappush(heap_small, -heapq.heappop(heap_large))\n",
    "                balance -= 2\n",
    "            elif balance < 0:\n",
    "                heapq.heappush(heap_large, -heapq.heappop(heap_small))\n",
    "                balance += 2\n",
    "            clear()\n",
    "\n",
    "        \n",
    "        for i in range(k, n):\n",
    "            add_num = nums[i]\n",
    "            del_num = nums[i-k]\n",
    "            if add_num == nums[i-k]:\n",
    "                ans.append(ans[-1])\n",
    "            else:\n",
    "                if not heap_large or add_num >= heap_large[0]:\n",
    "                    balance += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_large, add_num)\n",
    "                else:\n",
    "                    balance -= 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_small, -add_num)\n",
    "\n",
    "                del_cnts[del_num] += 1\n",
    "                if del_num >= heap_large[0]:\n",
    "                    balance -= 1\n",
    "                else:\n",
    "                    balance += 1\n",
    "                balance_heap()\n",
    "                if i>=k-1:\n",
    "                    ans.append(heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "import scipy\n",
    "\n",
    "class Solution(object):\n",
    "    def medianSlidingWindow(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[float]\n",
    "        \"\"\"\n",
    "        return [np.median(nums[i:i+k]) for i in range(len(nums)-k+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        heap_small = []\n",
    "        heap_large = []\n",
    "\n",
    "        large_size = small_size = 0\n",
    "        del_cnts = collections.defaultdict(int)\n",
    "\n",
    "        def clear():\n",
    "            while heap_large and del_cnts[heap_large[0]]:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                del_cnts[num] -= 1\n",
    "            while heap_small and del_cnts[-heap_small[0]]:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                del_cnts[-num] -= 1\n",
    "\n",
    "        def balance():\n",
    "            nonlocal large_size, small_size\n",
    "            clear()\n",
    "            if large_size > small_size+1:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                heapq.heappush(heap_small, -num)\n",
    "                large_size -= 1\n",
    "                small_size += 1\n",
    "            elif large_size < small_size:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                heapq.heappush(heap_large, -num)\n",
    "                large_size += 1\n",
    "                small_size -= 1\n",
    "            clear()\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            add_num = nums[i]\n",
    "            if i>=k and add_num == nums[i-k]:\n",
    "                ans.append(ans[-1])\n",
    "            else:\n",
    "                if not heap_large or add_num >= heap_large[0]:\n",
    "                    large_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_large, add_num)\n",
    "                else:\n",
    "                    small_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_small, -add_num)\n",
    "                if i >= k:\n",
    "                    del_num = nums[i-k]\n",
    "                    del_cnts[del_num] += 1\n",
    "                    if del_num >= heap_large[0]:\n",
    "                        large_size -= 1\n",
    "                    else:\n",
    "                        small_size -= 1\n",
    "                balance()\n",
    "                if i>=k-1:\n",
    "                    ans.append(heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        heap_small = []\n",
    "        heap_large = []\n",
    "\n",
    "        large_size = small_size = 0\n",
    "        del_cnts = collections.defaultdict(int)\n",
    "\n",
    "        def clear():\n",
    "            while heap_large and del_cnts[heap_large[0]]:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                del_cnts[num] -= 1\n",
    "            while heap_small and del_cnts[-heap_small[0]]:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                del_cnts[-num] -= 1\n",
    "\n",
    "        def balance():\n",
    "            nonlocal large_size, small_size\n",
    "            clear()\n",
    "            if large_size > small_size+1:\n",
    "                num = heapq.heappop(heap_large)\n",
    "                heapq.heappush(heap_small, -num)\n",
    "                large_size -= 1\n",
    "                small_size += 1\n",
    "            elif large_size < small_size:\n",
    "                num = heapq.heappop(heap_small)\n",
    "                heapq.heappush(heap_large, -num)\n",
    "                large_size += 1\n",
    "                small_size -= 1\n",
    "            clear()\n",
    "\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            add_num = nums[i]\n",
    "            if i>=k and add_num == nums[i-k]:\n",
    "                ans.append(ans[-1])\n",
    "            else:\n",
    "                if not heap_large or add_num >= heap_large[0]:\n",
    "                    large_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_large, add_num)\n",
    "                else:\n",
    "                    small_size += 1\n",
    "                    if del_cnts[add_num] > 0:\n",
    "                        del_cnts[add_num] -= 1\n",
    "                    else:\n",
    "                        heapq.heappush(heap_small, -add_num)\n",
    "                if i >= k:\n",
    "                    del_num = nums[i-k]\n",
    "                    del_cnts[del_num] += 1\n",
    "                    if del_num >= heap_large[0]:\n",
    "                        large_size -= 1\n",
    "                    else:\n",
    "                        small_size -= 1\n",
    "                balance()\n",
    "                if i>=k-1:\n",
    "                    ans.append(heap_large[0] if k&1 else (heap_large[0] - heap_small[0])/2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        import numpy as np\n",
    "        medians = np.zeros(len(nums) - k + 1)\n",
    "        for j in range(len(nums) - k + 1):\n",
    "            medians[j] = np.median(nums[j:j+k])\n",
    "        return medians"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        return [np.median(nums[i:i+k]) for i in range(len(nums)-k+1)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        if k==1:\n",
    "            return nums\n",
    "        d_del_left=defaultdict(int)\n",
    "        d_del_right=defaultdict(int)\n",
    "        left=[]\n",
    "        right=nums[:k]\n",
    "        heapify(right)\n",
    "        for _ in range(k//2):\n",
    "            heappush(left,-heappop(right))\n",
    "        odd = (k%2==1)\n",
    "        ans=[right[0]] if odd else [(right[0]-left[0])/2]\n",
    "        i = k\n",
    "        diff = target=1 if odd else 0\n",
    "        while i < len(nums):\n",
    "            num_del=nums[i-k]\n",
    "            num_add=nums[i]\n",
    "            # delete\n",
    "            if num_del<=-left[0]:\n",
    "                d_del_left[num_del]+=1\n",
    "                diff += 1\n",
    "            else:\n",
    "                d_del_right[num_del]+=1\n",
    "                diff -= 1\n",
    "            # add\n",
    "            if num_add<ans[-1]:\n",
    "                heappush(left,-num_add)\n",
    "                diff -= 1 \n",
    "            else:\n",
    "                heappush(right,num_add)\n",
    "                diff += 1\n",
    "\n",
    "            # adjust and delayed deleting\n",
    "            while True:\n",
    "                # print(left, right, d_del_left, d_del_right)\n",
    "                if right and d_del_right[right[0]]>0:\n",
    "                    nd=heappop(right)\n",
    "                    d_del_right[nd]-=1\n",
    "                elif left and d_del_left[-left[0]]>0:\n",
    "                    nd=-heappop(left)\n",
    "                    d_del_left[nd]-=1\n",
    "                elif diff<target:\n",
    "                    heappush(right,-heappop(left))\n",
    "                    diff+=2\n",
    "                elif diff>target:\n",
    "                    heappush(left,-heappop(right))\n",
    "                    diff-=2\n",
    "                else:\n",
    "                    break\n",
    "            # print(i, left,right)\n",
    "            if target==1:\n",
    "                ans.append(right[0])\n",
    "            else:\n",
    "                ans.append((right[0]-left[0])/2)\n",
    "            i+=1\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        if k == 1:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        mx = n+1\n",
    "        bit = [0]*mx\n",
    "        ans = []\n",
    "        def lowbit(i):\n",
    "            return i&-i\n",
    "        def update(i,val):\n",
    "            while i < mx:\n",
    "                bit[i] += val\n",
    "                i += lowbit(i)\n",
    "        def query(i):\n",
    "            res = 0\n",
    "            while i > 0:\n",
    "                res += bit[i]\n",
    "                i -= lowbit(i)\n",
    "            return res\n",
    "        def bs(cnt):\n",
    "            idx = bisect_left(range(1,mx),True,key=lambda x:query(x-1)>cnt)\n",
    "            return orgVal[idx]\n",
    "        def getMid():\n",
    "            return (bs(k//2) + bs((k-1)//2)) /2 \n",
    "        rank,orgVal = {},[-1]*mx\n",
    "        for i,j in enumerate(sorted(nums),1):\n",
    "            rank[j] = i\n",
    "            orgVal[i] = j\n",
    "        for i in range(k):\n",
    "            cur = nums[i]\n",
    "            update(rank[cur],1)\n",
    "        ans.append(getMid())\n",
    "        for i in range(k,n):\n",
    "            pre = nums[i-k]\n",
    "            cur = nums[i]\n",
    "            update(rank[cur],1)\n",
    "            update(rank[pre],-1)\n",
    "            ans.append(getMid())\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        lefts, rights = [], []\n",
    "        len_lefts, len_rights = 0, 0\n",
    "        left_num_count, right_num_count = dict(), dict()\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            start = i-k+1\n",
    "            if start > 0:\n",
    "                num_ = nums[start-1]\n",
    "                if left_num_count.get(num_,0) > 0:\n",
    "                    left_num_count[num_] -= 1\n",
    "                    len_lefts -= 1\n",
    "                else:\n",
    "                    right_num_count[num_] -= 1\n",
    "                    len_rights -= 1\n",
    "            num = nums[i]\n",
    "            if len_lefts <= len_rights:\n",
    "                if num not in right_num_count:\n",
    "                    heapq.heappush(rights, num)\n",
    "                right_num_count[num] = right_num_count.get(num,0)+1\n",
    "                while(right_num_count[rights[0]] == 0):\n",
    "                    del right_num_count[heapq.heappop(rights)]\n",
    "                num_ = rights[0]\n",
    "                right_num_count[num_] -= 1\n",
    "                if num_ not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num_)\n",
    "                left_num_count[num_] = left_num_count.get(num_,0)+1\n",
    "                len_lefts += 1\n",
    "            else:\n",
    "                if num not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num)\n",
    "                left_num_count[num] = left_num_count.get(num,0)+1\n",
    "                while(left_num_count[-lefts[0]] == 0):\n",
    "                    del left_num_count[-heapq.heappop(lefts)]\n",
    "                num_ = -lefts[0]\n",
    "                left_num_count[num_] -= 1\n",
    "                if num_ not in right_num_count:\n",
    "                    heapq.heappush(rights, num_)\n",
    "                right_num_count[num_] = right_num_count.get(num_,0)+1\n",
    "                len_rights += 1\n",
    "            while(left_num_count[-lefts[0]] == 0):\n",
    "                del left_num_count[-heapq.heappop(lefts)]\n",
    "            while(len(rights)>0 and right_num_count[rights[0]] == 0):\n",
    "                del right_num_count[heapq.heappop(rights)]\n",
    "            if len_lefts == len_rights:\n",
    "                res.append((rights[0]-lefts[0])/2)\n",
    "            else:\n",
    "                res.append(-lefts[0])\n",
    "            \n",
    "        return res[k-1:]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        lefts = []\n",
    "        rights = []\n",
    "        len_lefts = 0\n",
    "        len_rights = 0\n",
    "        left_num_count = dict()\n",
    "        right_num_count = dict()\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            start = i-k+1\n",
    "            if start > 0:\n",
    "                num_ = nums[start-1]\n",
    "                if left_num_count.get(num_,0) > 0:\n",
    "                    left_num_count[num_] -= 1\n",
    "                    len_lefts -= 1\n",
    "                else:\n",
    "                    right_num_count[num_] -= 1\n",
    "                    len_rights -= 1\n",
    "            num = nums[i]\n",
    "            if len_lefts <= len_rights:\n",
    "                if num not in right_num_count:\n",
    "                    heapq.heappush(rights, num)\n",
    "                right_num_count[num] = right_num_count.get(num,0)+1\n",
    "                while(right_num_count[rights[0]] == 0):\n",
    "                    del right_num_count[heapq.heappop(rights)]\n",
    "                num_ = rights[0]\n",
    "                right_num_count[num_] -= 1\n",
    "                if num_ not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num_)\n",
    "                left_num_count[num_] = left_num_count.get(num_,0)+1\n",
    "                len_lefts += 1\n",
    "            else:\n",
    "                if num not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num)\n",
    "                left_num_count[num] = left_num_count.get(num,0)+1\n",
    "                while(left_num_count[-lefts[0]] == 0):\n",
    "                    del left_num_count[-heapq.heappop(lefts)]\n",
    "                num_ = -lefts[0]\n",
    "                left_num_count[num_] -= 1\n",
    "                if num_ not in right_num_count:\n",
    "                    heapq.heappush(rights, num_)\n",
    "                right_num_count[num_] = right_num_count.get(num_,0)+1\n",
    "                len_rights += 1\n",
    "            while(left_num_count[-lefts[0]] == 0):\n",
    "                del left_num_count[-heapq.heappop(lefts)]\n",
    "            while(len(rights)>0 and right_num_count[rights[0]] == 0):\n",
    "                del right_num_count[heapq.heappop(rights)]\n",
    "            if len_lefts == len_rights:\n",
    "                res.append((rights[0]-lefts[0])/2)\n",
    "            else:\n",
    "                res.append(-lefts[0])\n",
    "            \n",
    "        return res[k-1:]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        n = len(nums)\n",
    "        lefts = []\n",
    "        rights = []\n",
    "        len_lefts = 0\n",
    "        len_rights = 0\n",
    "        left_num_count = dict()\n",
    "        right_num_count = dict()\n",
    "        res = []\n",
    "        for i in range(n):\n",
    "            start = i-k+1\n",
    "            if start > 0:\n",
    "                num_ = nums[start-1]\n",
    "                if left_num_count.get(num_,0) > 0:\n",
    "                    left_num_count[num_] -= 1\n",
    "                    len_lefts -= 1\n",
    "                else:\n",
    "                    right_num_count[num_] -= 1\n",
    "                    len_rights -= 1\n",
    "            num = nums[i]\n",
    "            if len_lefts <= len_rights:\n",
    "                if num not in right_num_count:\n",
    "                    heapq.heappush(rights, num)\n",
    "                right_num_count[num] = right_num_count.get(num,0)+1\n",
    "                while(right_num_count[rights[0]] == 0):\n",
    "                    del right_num_count[heapq.heappop(rights)]\n",
    "                num_ = rights[0]\n",
    "                right_num_count[num_] -= 1\n",
    "                if num_ not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num_)\n",
    "                left_num_count[num_] = left_num_count.get(num_,0)+1\n",
    "                len_lefts += 1\n",
    "            else:\n",
    "                if num not in left_num_count:\n",
    "                    heapq.heappush(lefts, -num)\n",
    "                left_num_count[num] = left_num_count.get(num,0)+1\n",
    "                while(left_num_count[-lefts[0]] == 0):\n",
    "                    del left_num_count[-heapq.heappop(lefts)]\n",
    "                num_ = -lefts[0]\n",
    "                left_num_count[num_] -= 1\n",
    "                if num_ not in right_num_count:\n",
    "                    heapq.heappush(rights, num_)\n",
    "                right_num_count[num_] = right_num_count.get(num_,0)+1\n",
    "                len_rights += 1\n",
    "            # print(lefts, len_lefts)\n",
    "            # print(rights, len_rights)\n",
    "            # print(left_num_count)\n",
    "            # print(right_num_count)\n",
    "            while(left_num_count[-lefts[0]] == 0):\n",
    "                del left_num_count[-heapq.heappop(lefts)]\n",
    "            while(len(rights)>0 and right_num_count[rights[0]] == 0):\n",
    "                del right_num_count[heapq.heappop(rights)]\n",
    "            if len_lefts == len_rights:\n",
    "                res.append((rights[0]-lefts[0])/2)\n",
    "            else:\n",
    "                res.append(-lefts[0])\n",
    "            \n",
    "        return res[k-1:]\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#直接用python中的bisect_left函数\n",
    "# class Solution:\n",
    "#     def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "#         n = len(nums)\n",
    "#         window = []\n",
    "\n",
    "#         ans = []\n",
    "#         for i in range(n):\n",
    "#             idx = bisect_left(window, nums[i]) #idx是window中的位置\n",
    "#             window[idx:idx] = [nums[i]] #插入新窗口的位置\n",
    "\n",
    "#             if len(window) > k:\n",
    "#                 q = nums[i - k]\n",
    "#                 idx = bisect_left(window, q)\n",
    "#                 window[idx : idx + 1] = []\n",
    "\n",
    "#             if len(window) == k:\n",
    "#                 median = (window[k // 2] + window[(k - 1) // 2]) / 2 #求取中位数\n",
    "#                 ans.append(median)\n",
    "\n",
    "#         return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        #用一个最大堆，存储小于中位数的数，用一个最小堆存储大于中位数的数\n",
    "        #两个堆的数目要么相等要么相差1\n",
    "        min_heap,max_heap = [],[]\n",
    "\n",
    "        # 初始化\n",
    "        for i in range(k):\n",
    "            heapq.heappush(min_heap,(nums[i],i))\n",
    "        for i in range(k//2):\n",
    "            n,idx = heapq.heappop(min_heap)\n",
    "            heapq.heappush(max_heap,(-n,idx))\n",
    "        \n",
    "        #分奇偶求出res\n",
    "        res = [(min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0]\n",
    "        \n",
    "        for i in range(k,len(nums)):\n",
    "            # 如果新数字应该放到最大堆\n",
    "            if nums[i] < min_heap[0][0]:\n",
    "                heapq.heappush(max_heap,(-nums[i],i)) #此时最大堆和最小堆一样或者多1\n",
    "                # 如果要弹出的元素在最小堆中，调整，保证最大堆和最小堆的个数相等\n",
    "                if nums[i-k] >= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(max_heap)\n",
    "                    heapq.heappush(min_heap,(-n,idx))\n",
    "            else: #新加进来的nums[i]如果和min_heap[0][0]相等的话\n",
    "                heapq.heappush(min_heap,(nums[i],i))\n",
    "                # 如果要弹出的元素在最大堆中，调整\n",
    "                # 取等号是特殊情况,也要从min里面弹出来到max堆中\n",
    "                if nums[i-k] <= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(min_heap)\n",
    "                    heapq.heappush(max_heap,(-n,idx))\n",
    "            \n",
    "            # 将堆顶在窗口外的元素清除出去\n",
    "            while min_heap and min_heap[0][1] <= i-k:\n",
    "                heapq.heappop(min_heap)\n",
    "            while max_heap and max_heap[0][1] <= i-k:\n",
    "                heapq.heappop(max_heap)\n",
    "            \n",
    "            # 添加答案\n",
    "            res.append((min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0)\n",
    "            \n",
    "        return res\n",
    "\n",
    "# 作者：musiala\n",
    "# 链接：https://leetcode-cn.com/problems/sliding-window-median/solution/python-shuang-dui-shuang-ha-xi-dui-liang-jb34/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        l, h = [], []\n",
    "        for i in range(k):\n",
    "            heappush(l, (-nums[i], i))\n",
    "        for i in range(k // 2):\n",
    "            x, y = heappop(l)\n",
    "            heappush(h, (-x, y))\n",
    "        ans = []\n",
    "        if k % 2 == 0:\n",
    "            ans.append((h[0][0] - l[0][0]) / 2)\n",
    "        else:\n",
    "            ans.append(-l[0][0])\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] >= -l[0][0]:\n",
    "                heappush(h, (nums[i], i))\n",
    "                if nums[i - k] <= -l[0][0]:\n",
    "                    x, y = heappop(h)\n",
    "                    heappush(l, (-x, y))\n",
    "            else:\n",
    "                heappush(l, (-nums[i], i))\n",
    "                if nums[i - k] >= -l[0][0]:\n",
    "                    x, y = heappop(l)\n",
    "                    heappush(h, (-x, y))\n",
    "            while l and l[0][1] <= i - k:\n",
    "                heappop(l)\n",
    "            while h and h[0][1] <= i - k:\n",
    "                heappop(h)\n",
    "            if k % 2 == 0:\n",
    "                ans.append((h[0][0] - l[0][0]) / 2)\n",
    "            else:\n",
    "                ans.append(-l[0][0])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        import heapq\n",
    "        #存放小于中位数的数\n",
    "        max_heap=[]\n",
    "        #存放大于中位数数\n",
    "        min_heap=[]\n",
    "        for i in range(k):\n",
    "            heapq.heappush(min_heap,(nums[i],i))\n",
    "        for i in range(k//2):\n",
    "            n,idx=heapq.heappop(min_heap)\n",
    "            heapq.heappush(max_heap,(-n,idx))\n",
    "        res = [(min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0]\n",
    "        \n",
    "        for i in range(k,len(nums)):\n",
    "            # 如果新数字应该放到最大堆\n",
    "            if nums[i] < min_heap[0][0]:\n",
    "                heapq.heappush(max_heap,(-nums[i],i))\n",
    "                # 如果要弹出的元素在最小堆中，调整\n",
    "                if nums[i-k] >= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(max_heap)\n",
    "                    heapq.heappush(min_heap,(-n,idx))\n",
    "            else:\n",
    "                heapq.heappush(min_heap,(nums[i],i))\n",
    "                # 如果要弹出的元素在最大堆中，调整\n",
    "                # 取等号是特殊情况\n",
    "                if nums[i-k] <= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(min_heap)\n",
    "                    heapq.heappush(max_heap,(-n,idx))\n",
    "            \n",
    "            # 将堆顶在窗口外的元素清除出去\n",
    "            while min_heap and min_heap[0][1] <= i-k:\n",
    "                heapq.heappop(min_heap)\n",
    "            while max_heap and max_heap[0][1] <= i-k:\n",
    "                heapq.heappop(max_heap)\n",
    "            \n",
    "            # 添加答案\n",
    "            res.append((min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# leetcode submit region begin(Prohibit modification and deletion)\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        lst, rst = [], []  # 左边大顶堆，右边小顶堆\n",
    "        for i in range(k):\n",
    "            heapq.heappush(lst, (-nums[i], -i))\n",
    "        for i in range(k // 2):\n",
    "            num, idx = heapq.heappop(lst)\n",
    "            heapq.heappush(rst, (-num, -idx))\n",
    "        if k % 2:\n",
    "            flg = 1\n",
    "        else:\n",
    "            flg = 0\n",
    "        l, r = len(lst), len(rst)\n",
    "        ans = [-lst[0][0] / 1.0 if (l - r) % 2 else -(lst[0][0] - rst[0][0]) / 2.0]\n",
    "        for i in range(k, len(nums)):\n",
    "            pop_num = nums[i - k]\n",
    "            if pop_num <= -lst[0][0]:\n",
    "                l -= 1\n",
    "            elif pop_num > -lst[0][0]:\n",
    "                r -= 1\n",
    "            heapq.heappush(rst, (nums[i], i))\n",
    "            r += 1\n",
    "            num, idx = heapq.heappop(rst)\n",
    "            if idx > i - k:\n",
    "                heapq.heappush(lst, (-num, -idx))\n",
    "                r -= 1\n",
    "                l += 1\n",
    "            while l - r != flg:\n",
    "                if l - r > flg:\n",
    "                    num, idx = heapq.heappop(lst)\n",
    "                    heapq.heappush(rst, (-num, -idx))\n",
    "                    l -= 1\n",
    "                    r += 1\n",
    "                if l - r < flg:\n",
    "                    num, idx = heapq.heappop(rst)\n",
    "                    heapq.heappush(lst, (-num, -idx))\n",
    "                    l += 1\n",
    "                    r -= 1\n",
    "            while lst and -lst[0][1] <= i - k:\n",
    "                heapq.heappop(lst)\n",
    "            while rst and rst[0][1] <= i - k:\n",
    "                heapq.heappop(rst)\n",
    "            ans.append(-lst[0][0] / 1.0 if (l - r) % 2 else -(lst[0][0] - rst[0][0]) / 2.0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "print(Solution().medianSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7],\n",
    "                                     3))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        small, large = [], []\n",
    "        for i, x in enumerate(nums[:k]): \n",
    "            heapq.heappush(small, (-x,i))\n",
    "        for _ in range(k-(k>>1)): \n",
    "            self.move(small, large)\n",
    "        ans = [self.get_med(small, large, k)]\n",
    "        for i, x in enumerate(nums[k:]):\n",
    "            if x >= large[0][0]:\n",
    "                heapq.heappush(large, (x, i+k))\n",
    "                if nums[i] <= large[0][0]: \n",
    "                    self.move(large, small)\n",
    "            else:\n",
    "                heapq.heappush(small, (-x, i+k))\n",
    "                if nums[i] >= large[0][0]: \n",
    "                    self.move(small, large)\n",
    "            while small and small[0][1] <= i: \n",
    "                heapq.heappop(small)\n",
    "            while large and large[0][1] <= i: \n",
    "                heapq.heappop(large)\n",
    "            ans.append(self.get_med(small, large, k))\n",
    "        return ans\n",
    "\n",
    "    def move(self, h1, h2):\n",
    "        x, i = heapq.heappop(h1)\n",
    "        heapq.heappush(h2, (-x, i))\n",
    "        \n",
    "    def get_med(self, h1, h2, k):\n",
    "        return h2[0][0] * 1. if k & 1 else (h2[0][0]-h1[0][0]) / 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        import heapq\n",
    "        left, right = [(float('inf'), float('inf'))], [(float('inf'), float('inf'))]  # left: -val, index| right: val, index\n",
    "        lrm, rrm = 0, 0\n",
    "        res = []\n",
    "        for i, x in enumerate(nums):\n",
    "            leftmax = -left[0][0]\n",
    "            rightmin = right[0][0]\n",
    "            if x < rightmin:\n",
    "                heapq.heappush(left, (-x, i))\n",
    "                leftmax = -left[0][0]\n",
    "            else:\n",
    "                heapq.heappush(right, (x, i))\n",
    "                rightmin = right[0][0]\n",
    "            if i >= k:\n",
    "                rm_target = nums[i-k]\n",
    "                if rm_target < leftmax:\n",
    "                    lrm += 1\n",
    "                elif rm_target > rightmin:\n",
    "                    rrm += 1\n",
    "                else:\n",
    "                    if len(right) == 1 or left[0][1] < right[0][1]:\n",
    "                        lrm += 1\n",
    "                    else:\n",
    "                        rrm += 1\n",
    "            while (len(left)-lrm) - (len(right)-rrm) < k % 2:\n",
    "                t, j = heapq.heappop(right)\n",
    "                if j <= i - k:\n",
    "                    rrm -= 1\n",
    "                else:\n",
    "                    heapq.heappush(left, (-t, j))\n",
    "            while (len(left)-lrm) - (len(right)-rrm) > k % 2:\n",
    "                t, j = heapq.heappop(left)\n",
    "                if j <= i - k:\n",
    "                    lrm -= 1\n",
    "                else:\n",
    "                    heapq.heappush(right, (-t, j))\n",
    "            while left[0][1] <= i - k:\n",
    "                heapq.heappop(left)\n",
    "                lrm -= 1\n",
    "            while right[0][1] <= i - k:\n",
    "                heapq.heappop(right)\n",
    "                rrm -= 1\n",
    "            if i >= k-1:\n",
    "                if k % 2:\n",
    "                    res.append(-left[0][0])\n",
    "                else:\n",
    "                    res.append((-left[0][0] + right[0][0])/2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        min_heap, max_heap = [], []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(min_heap, (nums[i], i))\n",
    "        for i in range(k // 2):\n",
    "            n, idx = heapq.heappop(min_heap)\n",
    "            heapq.heappush(max_heap, (-n, idx))\n",
    "        res = [(min_heap[0][0] - max_heap[0][0]) / 2 if k % 2 == 0 else min_heap[0][0] * 1.0]\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] < min_heap[0][0]:\n",
    "                heapq.heappush(max_heap, (-nums[i], i))\n",
    "                if nums[i - k] >= min_heap[0][0]:\n",
    "                    n, idx = heapq.heappop(max_heap)\n",
    "                    heapq.heappush(min_heap, (-n, idx))\n",
    "            else:\n",
    "                heapq.heappush(min_heap, (nums[i], i))\n",
    "                if nums[i - k] <= min_heap[0][0]:\n",
    "                    n, idx = heapq.heappop(min_heap)\n",
    "                    heapq.heappush(max_heap, (-n, idx))\n",
    "            while min_heap and min_heap[0][1] <= i - k:\n",
    "                heapq.heappop(min_heap)\n",
    "            while max_heap and max_heap[0][1] <= i - k:\n",
    "                heapq.heappop(max_heap)\n",
    "            res.append((min_heap[0][0] - max_heap[0][0]) / 2 if k % 2 == 0 else min_heap[0][0] * 1.0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        min_heap, max_heap = [], []\n",
    "        for i in range(k):\n",
    "            heapq.heappush(min_heap, (nums[i], i))\n",
    "        for i in range( k // 2):\n",
    "            val, idx = heapq.heappop(min_heap)\n",
    "            heapq.heappush(max_heap, (-val, idx))\n",
    "        \n",
    "        res = [min_heap[0][0] if k % 2 == 1 else (min_heap[0][0] - max_heap[0][0]) / 2]\n",
    "\n",
    "        for i in range(k, len(nums)):\n",
    "            if nums[i] < min_heap[0][0]:\n",
    "                heapq.heappush(max_heap, (-nums[i], i))\n",
    "                if nums[i-k] >= min_heap[0][0]:\n",
    "                    val, idx = heapq.heappop(max_heap)\n",
    "                    heapq.heappush(min_heap, (-val, idx))\n",
    "            else:\n",
    "                heapq.heappush(min_heap, (nums[i], i))\n",
    "                if nums[i-k] <= min_heap[0][0]:\n",
    "                    val, idx = heapq.heappop(min_heap)\n",
    "                    heapq.heappush(max_heap, (-val, idx))\n",
    "\n",
    "            while min_heap and min_heap[0][1] <= i-k:\n",
    "                heapq.heappop(min_heap)\n",
    "            while max_heap and max_heap[0][1] <= i-k:\n",
    "                heapq.heappop(max_heap)\n",
    "\n",
    "            res.append(min_heap[0][0] if k % 2 == 1 else (min_heap[0][0] - max_heap[0][0]) / 2)\n",
    "        return res\n",
    "\n",
    "\n",
    "        # https://leetcode.cn/problems/sliding-window-median/solution/python-shuang-dui-shuang-ha-xi-dui-liang-jb34/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        min_heap,max_heap = [],[]\n",
    "\n",
    "        # 初始化\n",
    "        for i in range(k):\n",
    "            heapq.heappush(min_heap,(nums[i],i))\n",
    "        for i in range(k//2):\n",
    "            n,idx = heapq.heappop(min_heap)\n",
    "            heapq.heappush(max_heap,(-n,idx))\n",
    "        \n",
    "        res = [(min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0]\n",
    "        \n",
    "        for i in range(k,len(nums)):\n",
    "            # 如果新数字应该放到最大堆\n",
    "            if nums[i] < min_heap[0][0]:\n",
    "                heapq.heappush(max_heap,(-nums[i],i))\n",
    "                # 如果要弹出的元素在最小堆中，调整\n",
    "                if nums[i-k] >= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(max_heap)\n",
    "                    heapq.heappush(min_heap,(-n,idx))\n",
    "            else:\n",
    "                heapq.heappush(min_heap,(nums[i],i))\n",
    "                # 如果要弹出的元素在最大堆中，调整\n",
    "                # 取等号是特殊情况\n",
    "                if nums[i-k] <= min_heap[0][0]:\n",
    "                    n,idx = heapq.heappop(min_heap)\n",
    "                    heapq.heappush(max_heap,(-n,idx))\n",
    "            \n",
    "            # 将堆顶在窗口外的元素清除出去\n",
    "            while min_heap and min_heap[0][1] <= i-k:\n",
    "                heapq.heappop(min_heap)\n",
    "            while max_heap and max_heap[0][1] <= i-k:\n",
    "                heapq.heappop(max_heap)\n",
    "            \n",
    "            # 添加答案\n",
    "            res.append((min_heap[0][0]-max_heap[0][0])/2 if k % 2 == 0 else min_heap[0][0] * 1.0)\n",
    "            \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:\n",
    "        if k == 1:\n",
    "            return [float(num) for num in nums]  # 如果窗口大小为1，直接返回每个元素的浮点数形式的列表\n",
    "\n",
    "        res = []  # 存储中位数的结果列表\n",
    "        mid_cnt = k // 2  # 窗口的中位数索引\n",
    "\n",
    "        # 初始化两个堆，info1用于存储较大一半的元素（负值），info2用于存储较小一半的元素\n",
    "        info1 = [(-num, i) for i, num in enumerate(nums[:mid_cnt])]\n",
    "        info2 = []\n",
    "\n",
    "        heapq.heapify(info1)  # 将info1转化为最小堆\n",
    "\n",
    "        def get_median(info1, info2, k):\n",
    "            # 辅助函数，计算中位数\n",
    "            if k % 2 == 0:\n",
    "                return (-info1[0][0] + info2[0][0]) / 2.0\n",
    "            else:\n",
    "                return float(info2[0][0])\n",
    "\n",
    "        # 初始窗口滑动过程\n",
    "        for i in range(mid_cnt, k):\n",
    "            if nums[i] < -info1[0][0]:\n",
    "                num, j = heapq.heappop(info1)  # 弹出info1的堆顶元素\n",
    "                heapq.heappush(info2, (-num, j))  # 将弹出的元素加入info2\n",
    "                heapq.heappush(info1, (-nums[i], i))  # 将新元素加入info1\n",
    "            else:\n",
    "                heapq.heappush(info2, (nums[i], i))  # 将新元素加入info2\n",
    "\n",
    "        res.append(get_median(info1, info2, k))  # 计算并添加初始窗口的中位数\n",
    "\n",
    "        i = k\n",
    "        while i < len(nums):\n",
    "            num, j = nums[i - k], i - k  # 要移出窗口的元素和其索引\n",
    "\n",
    "            if num <= -info1[0][0]:\n",
    "                if nums[i] < info2[0][0]:\n",
    "                    heapq.heappush(info1, (-nums[i], i))  # 新元素加入info1\n",
    "                else:\n",
    "                    num1, i1 = info2[0]\n",
    "                    heapq.heappush(info1, (-num1, i1))  # info2的堆顶元素加入info1\n",
    "                    heapq.heapreplace(info2, (nums[i], i))  # 弹出info2的堆顶并加入新元素\n",
    "            else:\n",
    "                if nums[i] < -info1[0][0]:\n",
    "                    num1, i1 = info1[0]\n",
    "                    heapq.heappush(info2, (-num1, i1))  # info1的堆顶元素加入info2\n",
    "                    heapq.heapreplace(info1, (-nums[i], i))  # 弹出info1的堆顶并加入新元素\n",
    "                else:\n",
    "                    heapq.heappush(info2, (nums[i], i))  # 新元素加入info2\n",
    "\n",
    "            while info1[0][1] <= j:\n",
    "                heapq.heappop(info1)  # 移出info1中已经不在窗口中的元素\n",
    "            while info2[0][1] <= j:\n",
    "                heapq.heappop(info2)  # 移出info2中已经不在窗口中的元素\n",
    "\n",
    "            res.append(get_median(info1, info2, k))  # 计算并添加当前窗口的中位数\n",
    "            i += 1  # 窗口右移一位\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
